Gautier Berthou

Vivien Quéma

FastCast: a Throughput-and Latency-efficient Total Order Broadcast Protocol

Many uniform total order broadcast protocols have been designed in the last 30 years. Unfortunately, none of them achieves both optimal throughput and low latency. Indeed, protocols achieving optimal throughput rely on a ring dissemination pattern, which induces high latencies. Protocols achieving low latency rely on IP multicast and fail to achieve good throughput because of message losses. In this paper, we describe FastCast, the first protocol that achieves both optimal throughput and low latency. To achieve low latency, FastCast relies on IP multicast. To achieve optimal throughput, FastCast defines a protocol responsible for dynamically computing the throughput at which processes can send IP multicast messages. Thanks to this dynamic bandwidth allocation protocol, FastCast allows multiple processes to simultaneously send messages, while avoiding message losses. An evaluation of FastCast on a cluster of 8 machines shows that it indeed achieves optimal throughput and a very low latency.

Introduction

State-machine replication [START_REF] Schneider | Implementing fault-tolerant services using the state machine approach: a tutorial[END_REF] is a popular technique to ensure fault-tolerance in computer systems. The operating principle of state-machine replication is simple: several replicas of the same software object are maintained on different machines (also called processes). Each replica executes the same requests in the same order and is thus consistent with other replicas. Consequently, if one or more replicas fail, remaining replicas are consistent and guarantee accessibility to the object. To ensure that replicas execute requests in the same order, each replica broadcasts the requests it receives to other replicas using a uniform total order broadcast [START_REF] Hadzilacos | Fault-tolerant broadcasts and related problems[END_REF], and executes requests in the order in which they are delivered by the protocol. A uniform total order broadcast protocol ensures the following properties for all messages that are broadcast: (1) Uniform agreement: if a replica delivers a message m, then all correct replicas eventually deliver m; (2) Strong uniform total order: if some replica delivers some message m before message m , then a replica delivers m only after it has delivered m.

Many uniform total order broadcast protocols have been designed in the last 30 years [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. They can be classified into two categories: those targeting low latency, and those targeting high throughput. Latency measures the time required to complete a single message broadcast without contention, whereas throughput measures the number of broadcasts that the processes can complete per time unit when there is contention.

Protocols targeting low latency usually rely on IP multicast, a low-level networking protocol allowing senders to reach multiples destinations using a single message. These protocols do not achieve high throughput for the following reason: IP multicast messages are dropped when the network is congested. To limit congestion, protocols are designed in such a way that only one process at a time can send IP multicast messages. As we explain in Section 3.2, this does not allow achieving optimal throughput. Protocols targeting high (actually optimal) throughput [START_REF] Guerraoui | High Throughput Total Order Broadcast for Cluster Environments[END_REF][START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF] organize processes in a virtual ring topology: each process only communicates with its successor on the ring, using a reliable point-to-point communication protocol: TCP. These protocols achieve significantly higher throughput than protocols targeting low latency, e.g. +25% in a system comprising 4 processes. Nevertheless, these protocols have a significant drawback: because of the ring topology they rely on, latency linearly increases with the number of processes in the system.

In this paper, we present, FastCast, the first protocol that achieves both optimal throughput3 and low latency. To achieve low latency, FastCast relies on IP multicast. To achieve optimal throughput, FastCast allows multiple processes to simultaneously send IP multicast messages. Message ordering is achieved by a fairly classical fixed-sequencer scheme [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. The novelty in FastCast lies in a subprotocol executed by all processes that dynamically computes at which throughput each process can send IP multicast messages.

We have implemented FastCast in C++ and have compared its performance to that achieved by two recent state-of-the-art protocols: LCR [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF] and Ring-Paxos [START_REF] Marandi | Ring paxos: A high-throughput atomic broadcast protocol[END_REF]. The former achieves optimal throughput, whereas the latter aims at achieving both high throughput and low latency. Our evaluation on a cluster of 8 machines shows that FastCast achieves optimal throughput and very low latency. More precisely, FastCast achieves up to 86% faster throughput than RingPaxos, and up to 247% lower latency than LCR.

This paper is organized as follows. Section 2 gives a brief overview of the related work. Section 3 presents the FastCast protocol. A detailed performance evaluation is provided in Section 4, before concluding the paper in Section 5.

Related Work

Various total order broadcast protocols have been devised during the past 30 years [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. We can distinguish two classes of protocols: those providing uniform agreement and those providing non-uniform agreement. In uniform agreement protocols, if a process delivers a message, then all correct processes will eventually deliver it. This is not necessarily the case in non-uniform protocols: if a node delivers a message and subsequently fail, the message might not be delivered by remaining (correct) processes. Total order broadcast protocols ensuring uniform agreement are more complex to implement and are often less efficient than non-uniform protocols. Nevertheless, they can be used for a much broader sets of applications. Consequently, the protocol we propose in this paper implements uniform agreement. In the remainder of this section, we do thus put more emphasis on uniform total order broadcast protocols.

Défago and Schiper have written an extensive survey on total order broadcast protocols [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. They distinguish five types of total order broadcast protocols: fixed-sequencer, moving sequencer, privilege-based, communication history, and destination agreement. As is explained in the survey [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF], "communication history" and "destination agreement" protocols [START_REF] Peterson | Preserving and using context information in interprocess communication[END_REF][START_REF] Malhis | Numerical performability evaluation of a group multicast protocol[END_REF][START_REF] Ezhilchelvan | Newtop: a fault-tolerant group communication protocol[END_REF][START_REF] Ng | Ordered broadcasts for large applications[END_REF][START_REF] Moser | Asynchronous fault-tolerant total ordering algorithms[END_REF][START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF][START_REF] Birman | Reliable communication in the presence of failures[END_REF][START_REF] Luan | A fault-tolerant protocol for atomic broadcast[END_REF][START_REF] Fritzke | Consensus-based faulttolerant total order multicast[END_REF][START_REF] Anceaume | A lightweight solution to uniform atomic broadcast for asynchronous systems[END_REF] are less efficient than other types protocols. The three other types of protocols work as follows. In a fixed sequencer protocol [START_REF] Marandi | Ring paxos: A high-throughput atomic broadcast protocol[END_REF][START_REF] Kaashoek | An evaluation of the amoeba group communication system[END_REF][START_REF] Armstrong | Multicast transport protocol[END_REF][START_REF] Carr | The tandem global update protocol[END_REF][START_REF] Garcia-Molina | Ordered and reliable multicast communication[END_REF][START_REF] Birman | Reliable Distributed Computing with the Isis Toolkit[END_REF][START_REF] Wilhelm | A hierarchy of totally ordered multicasts[END_REF][START_REF] Ban | JGroups -A Toolkit for Reliable Multicast Communication[END_REF], a single process is elected as the sequencer and is responsible for the ordering of messages. The sequencer is unique, and another process is elected as a new sequencer only in the case of sequencer failure. Moving sequencer protocols [START_REF] Chang | Reliable broadcast protocols[END_REF][START_REF] Whetten | A high performance totally ordered multicast protocol[END_REF][START_REF] Kim | A total ordering protocol using a dynamic token-passing scheme[END_REF][START_REF] Cristian | High-performance asynchronous atomic broadcast[END_REF] are based on the same principle as fixed sequencer protocols, but allow the role of the sequencer to be passed from one process to another (even in failure-free situations). This is achieved by a token which carries a sequence number and constantly circulates among the processes. The motivation is to distribute the load among sequencers, thus avoiding the bottleneck caused by a single sequencer. When a process p wants to broadcast a message m, it sends it to all other processes. Upon receiving m, processes store it into a receive queue. When the current token holder q has a message in its receive queue, q assigns a sequence number to the first message in the queue and broadcasts that message together with the token. For a message m to be delivered, it has to be acknowledged by all processes. Acks are gathered by the token. Finally, privilege-based protocols [START_REF] Friedman | Packing messages as a tool for boosting the performance of total ordering protocls[END_REF][START_REF] Cristian | Asynchronous atomic broadcast[END_REF][START_REF] Ekwall | Token-based atomic broadcast using unreliable failure detectors[END_REF][START_REF] Amir | The Totem single-ring ordering and membership protocol[END_REF][START_REF] Gopal | Reliable broadcast in synchronous and asynchronous environments (preliminary version)[END_REF][START_REF] Amir | The spread toolkit: Architecture and performance[END_REF] rely on the idea that senders can broadcast messages only when they are granted the privilege to do so. The privilege to broadcast (and order) messages is granted to only one process at a time, but this privilege circulates from process to process in the form of a token. As with moving sequencer protocols, the throughput when all processes broadcast cannot be higher than when only one process broadcasts.

All the protocols mentioned above have been designed with the goal to ensure low broadcast latency. Latency measures the time required to complete a single message broadcast without contention. As shown in [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF], above-mentioned protocols are far from sustaining optimal throughput. Throughput measures the number of broadcasts that the processes can complete per time unit. In some high load environments, e.g. database replication for e-commerce, throughput is often more important than latency. Indeed, under high load, the time spent by a message in a queue before being actually disseminated can grow indefinitely. A high throughput broadcast protocol reduces this waiting time. The authors of [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF] prove that in a system comprising N nodes interconnected by a fully-switched network where each link has a bandwidth of B, the optimal throughput that can be achieved by a total order broadcast protocol is equal to B * N/(N -1). For instance, in a system with 4 nodes interconnected by a gigabit ethernet switch (B=1Gb/s), each node can deliver messages at a throughput of 1,33Gb/s. The only protocol currently able to sustain that throughput is the LCR protocol [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF].

In other protocols, the maximum throughput at which a node can deliver messages is B (1Gb/s in the example taken before). This is for instance the case of protocols known to be efficient such as Spread [START_REF] Amir | The spread toolkit: Architecture and performance[END_REF], RingPaxos [START_REF] Marandi | Ring paxos: A high-throughput atomic broadcast protocol[END_REF], or the protocol designed by Chang and Maxemchuck [START_REF] Chang | Reliable broadcast protocols[END_REF]. The reason why these protocols do not achieve optimal throughput is that only one node at a time is allowed to broadcast a message. As explained in [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF], optimal throughput can only be achieved when all nodes are allowed to simultaneously broadcast messages. Throughputwise, LCR is thus much more efficient than other protocols. Nevertheless, the throughput-efficiency of LCR comes at a price: latency linearly increases with the number of nodes in the system. This comes from the fact that, in order to sustain high throughput, LCR uses a ring-based pipelining patterns: nodes are organized in a virtual ring. Each node only communicates with its successor in the ring. This pipelining pattern is efficient as it avoids message collisions, but it is not latency-efficient. In this paper, we propose a protocol that reaches optimal throughput, but that achieves a much lower latency than the LCR protocol.

The FastCast Protocol

In this section, we describe the FastCast protocol. We start by a description of the system model we consider. We then give an overview of FastCast, followed by a description of the three subprotocols that compose it.

System Model

We have designed the FastCast protocol for small clusters of homogeneous machines interconnected by a local area network. We assume that machines can only fail by crashing (i.e. Byzantine failures are out of the scope of this paper), that crashes are rare, and that each node is equipped with a perfect failure detector (P ) [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. A perfect failure detector outputs the list of alive processes and guarantees strong accuracy (correct machines are never suspected to have crashed) and strong completeness (every crash is eventually detected). In order to implement a perfect failure detector, each machine creates a TCP connection to all other machines and maintains this connection during the entire execution of the protocol (unless the machine fails). When a connection fails, the machine tries to re-establish it five times. If the machine does not succeed, it considers that the other machine crashed. This is a reasonable assumption provided that, on a cluster, the latency of the network interconnecting the machines is very low [START_REF] Dunagan | Fuse: Lightweight guaranteed distributed failure notification[END_REF].

Overview

Our goal is to design a uniform total order broadcast protocol achieving optimal throughput, while guaranteeing a low latency. In order to ensure low latency, the best option is to use IP multicast. Indeed, using IP multicast, a process can reach all other processes in the system sending a single message. This choice is natural and most total order broadcast protocols rely on IP multicast. Unfortunately, IP multicast is not reliable: messages are dropped as soon as the network gets congested.

In order to reduce the ratio of message losses, most state-of-the-art total order broadcast protocols rely on a simple technique: only one process is allowed to send IP multicast messages. That way, it is easy to avoid network congestion by controlling the rate at which the sending process broadcasts IP multicast messages. Unfortunately, using one single sender is not enough to reach optimal throughput. To clarify that point, we depict in Figure 1 a system comprising 3 nodes interconnected by a 1Gb/s ethernet switch. On the left part of the Figure, only one node sends IP multicast messages. The maximum throughput at which nodes of the system can deliver messages in that configuration is 1Gb/s. On the right part of the Figure, we display a configuration where the 3 nodes simultaneously send IP multicast messages. Each node sends at a throughput of 500Mb/s. In that configuration, the maximum throughput at which nodes of the system can deliver messages is equal to 1,5Gb/s: each node delivers 500Mb/s that it produces itself, and 1Gb/s that are sent by other nodes. This is explained by two facts: (i) network cables and Network Interface Cards (NIC) are full-duplex (i.e. a node can simultaneously send and receive messages on the same network cable), and (ii) switches only forward IP multicast messages to nodes other than the source (i.e. a node does not receive its own messages via the network). As the goal of FastCast is to reach optimal throughput while ensuring low latency, the protocol allows multiple processes to simultaneously send IP multicast messages. There are well-known algorithms for ensuring uniform total order of messages multicast by different senders [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. In this paper, our goal is not to design a new one. Therefore, we take the simplest one, called fixed-sequencer protocol (see Sections 3.3 and 3.4 for a short description). Rather, we focus on designing a subprotocol in charge of synchronizing the various senders (see Section 3.5). More precisely, our protocol allows every sender to gather the bandwidth requirements of other senders and to adapt its bandwidth accordingly (using a max-min fair bandwidth allocation algorithm [START_REF] Boudec | Rate adaptation, congestion control and fairness: A tutorial[END_REF]). The idea implemented by the protocol is simple and, as we show in Section 4, yields excellent performance.

Ordering Subprotocol

FastCast is a uniform total order broadcast protocol exporting two primitives, utoBroadcast and utoDeliver, and ensuring the following four properties:

-Validity: if a correct process p i utoBroadcasts a message m, then p i eventually utoDelivers m. -Integrity: for any message m, any correct process p j utoDelivers m at most once, and only if m was previously utoBroadcast by some correct process p i . -Uniform Agreement: if any process p i utoDelivers any message m, then every correct process p j eventually utoDelivers m. -Total Order: for any two messages m and m , if any process p i utoDelivers m without having delivered m , then no process p j utoDelivers m before m.

The ordering subprotocol implementing these four properties is given in Figure 2. This is a fairly classical fixed-sequencer pattern [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. One process is designated leader, and is in charge of assigning and broadcasting sequence numbers. It is important to notice that the leader is not in charge of forwarding content messages (named Data message in Figure 2). Rather, these are processes that are in charge of sending their Data messages to all other processes (line 10). In order to ensure uniform agreement on message delivery, every node acknowledges the reception of the messages and the sequence numbers associated with them (line 19 for the leader, and line 24 for other processes). Every node waits for an acknowledgment from all nodes before delivering a message (lines 30 and 31). That way, a node is sure that the message it delivers is known (together with its sequence number) by all other nodes and will thus be delivered by all correct nodes even if it subsequently fails. Note that to handle message losses, a node that broadcasts a message uses a timer (line 12). If after some amount of time, a node has not delivered its own message (i.e. the message is still in the pendings array as checked in line 35), it resends the message (line 36).

Membership Management Subprotocol

In order to handle nodes joining and leaving the system, the FastCast protocol is built on top of a group communication system [START_REF] Birman | Exploiting virtual synchrony in distributed systems[END_REF] relying on a perfect failure detector [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. Processes are organized into groups, which they can leave or join. When a process joins or leaves a group, this triggers a view change protocol. Thanks to the perfect failure detector, faulty processes are excluded from the group after crashing. Upon a membership change, processes agree on a new view: the current view v r is replaced by a new view v r+1 .

The view change procedure is detailed in Figure 3. Note that when a view change occurs, every process first completes the execution (if any) of all other procedures described in Figure 2. It then freezes those procedures and executes the view change procedure. The latter works as follows (Note that the view change functions make use of two primitives Rsend and Rreceive that implement reliable communication channels. In our implementation, these primitives are implemented using TCP): every process sends its pendings and seqnos arrays to all other processes (line 2). Upon receiving these arrays, every process updates its own pendings and seqnos arrays using those received from all other processes (lines 15 and 17). Then, the processes send back an Ack Recover message (line 18). Processes wait until they receive Ack Recover messages from all processes (line 3) before sending an End Recovery message to all (line 4). When a process receives End Recovery messages from all processes (line 5), it can deliver all the messages for which it has a sequence number (lines 19 to 24). Thus, at the end of the view change procedure, all processes belonging to the new view will have delivered the same messages in the same order. Each process then empties its pendings, seqnos and acks arrays (lines 8 to 10). Moreover, each process uses as new leader the first process in the new view (line 11). Fig. 3. Pseudo-code of the membership management subprotocol.

Bandwidth Allocation Subprotocol

In this section, we describe the bandwidth allocation protocol implemented in FastCast. We start by describing the principles underlying its design. We then comment a detailed pseudo-code. Finally, we give an illustration of its behavior.

Principles. The goal of the bandwidth allocation protocol is to allocate bandwidth for each sending node in order to allow multiple nodes to simultaneously send IP multicast packets, while avoiding message losses. As explained before, having multiple senders is a requirement to ensure that the full network capability is used. If we assume that at a given time, all nodes know the bandwidth requirements of all other nodes, it is easy to allocate bandwidth using a maxmin fair bandwidth allocation algorithm [START_REF] Boudec | Rate adaptation, congestion control and fairness: A tutorial[END_REF]. For instance, let us consider a system comprising 3 nodes interconnected by a 1Gb/s ethernet switch. Let us assume that each node knows that, e.g. node 1 requires 700Mb/s, node 2 requires 600Mb/s, and node 3 requires 300Mb/s. Each node can deterministically compute the following fair bandwidth allocation: 500Mb/s for nodes 1 and 2, and 300Mb/s for node 3. It is indeed not possible to allocate more than 500Mb/s to nodes 1 and 2. Otherwise, node 3 would have to receive messages at a higher throughput than 1Gb/s, which it cannot do. Indeed, the network link connecting node 3 to the switch has a capability of 1Gb/s. It is possible to design a protocol allowing nodes to exchange their bandwidth requirements and ensuring that every node knows, at any time, the bandwidth requirements of other nodes. Such a protocol would nevertheless be costly and would require to force all nodes to synchronize whenever one node wants to change its bandwidth. Interestingly, it is possible to fairly allocate bandwidth with a weaker requirement: it is enough that every node receive the various bandwidth requirements from other nodes in the same order. This property can be easily achieved by leveraging the FastCast protocol itself. Each time a node wants to modify its allocated bandwidth (e.g. to increase it, or to decrease it), it sends a message to all other nodes using the FastCast protocol. That way, all nodes receive the bandwidth requirement messages in the same order.

The question that remains to answer is: when can nodes actually modify their bandwidth? A node behaves differently depending on whether it requires a decrease of its bandwidth or an increase of its bandwidth. In the case of a bandwidth decrease, the node actually decreases its bandwidth before sending the message notifying other nodes. That way, when other nodes receive its notification message, they know that the node already decreased its bandwidth and they can recompute the bandwidth allocation and possibly decide to increase their own bandwidth. In the case of a bandwidth increase, a node n cannot directly increase its bandwidth (otherwise, that could congest the network). The node does thus first send the message notifying others that it wants to increase its bandwidth. Upon receiving the notification that node n wants to increase its bandwidth, other nodes locally recompute the bandwidth allocation (based on the new bandwidth requirement sent by node n) and possibly reduce their own bandwidth. Then, each node sends an acknowledgement to node n. It is only after it has received acknowledgments from all other nodes that node n can actually increase its bandwidth (by locally computing the bandwidth allocation).

Detailed Pseudo-code. Figure 4 gives the pseudo-code of the bandwidth allocation protocol. Every node stores the bandwidth requirements of other nodes in the bwRequirements array and its current bandwidth in the currentBW variable. The ongoing increase, delivered req, and acks fields are used when a node wants to increase its bandwidth: ongoing increase stores the required increase (before being stored in bwRequirements when all other processes will have acknowledged it); the delivered req field indicates whether the increase notification message has been delivered by the requiring node itself (if that is not the case, the requiring node cannot take its own request into account even if it received an acknowledgement from all other processes); finally, the acks field is used to count the number of acknowledgements that have been received for the ongoing bandwidth increase request.

Before going into the details of the protocol, let us remark that the BW allocation function (lines 34 to 47) implements a classical max-min fair bandwidth allocation algorithm [START_REF] Boudec | Rate adaptation, congestion control and fairness: A tutorial[END_REF]. The only important point to mention is that it uses a variable, called availableBW, that represents the maximum capability of a network link. This capability is dependent from the average message size (it is well-known that the larger the messages, the higher the throughput that can be achieved by a communication protocol [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF][START_REF] Marandi | Ring paxos: A high-throughput atomic broadcast protocol[END_REF]). In our implementation, we use 4kB as the average message size and set the value of availableBW to the capability that the network links exhibit when used with 4kB messages (this capability is close to the optimal one). To be sure that this is the actual capability that network links will have at runtime, the FastCast protocols batches messages to ensure that sent messages are at least 4kB large (unless there is no contention, in which case small messages can be sent as the protocol does not need to sustain high throughput in such cases).

Let us now describe the bandwidth allocation subprotocol. A node can either ask to increase its bandwidth (using the increase BW procedure at line 7) or to decrease it (using the decrease BW procedure at line 26). Let us first describe what happens when a node wants to increase its bandwidth. The node calls the increase BW procedure. Inside this procedure, the node utoBroadcasts an Incr message to all other processes (line 10). When delivering this message, other processes update their bwRequirements array (line 12), recompute the bandwidth allocation (line 13) using the BW allocation function, and sends an Ack message back to the requiring process (line 14). When the requiring node has both received an acknowledgement from all other nodes and delivered its own increase request (line 16), it updates its bwRequirements array (line 21) and recompute the bandwidth allocation (line 22).

Let us now describe what happens when a node wants to decrease its bandwidth. The node calls the decrease BW procedure. Inside this procedure, the node updates its bwRequirements array (line 28) and recompute the bandwidth allocation (line 29). The requiring node then utoBroadcasts a Decr message to all other processes (line 30). When delivering this message, other processes update their bwRequirements array (line 32) and recompute the bandwidth allocation (line 33), using the BW allocation function.

Illustration. We provide three illustrations of the bandwidth allocation protocol in Table 1, Table 2, and Table 3. We consider a system with 3 processes interconnected by a 1Gb/s switch. In each table, we describe a set of steps that happen in the system and we illustrate how the different fields of the three processes are updated. Initially, the three processes have a null bandwidth (currentBW is equal to 0 in Table 1, step S1). In Table 1 this initial state, p 0 calls increase BW(800) and p 1 calls increase BW(300). Processes reach a state (step S8) in which p 0 has its currentBW variable equal to 700Mb/s and p 1 has its currentBW variable equal to 300Mb/s. From that state (also depicted in Table 2, step S9), Table 2 depicts what happens when p 2 calls increase BW(600). Processes reach a state (step S13) in which p 0 and p 2 both have their currentBW variable equal to 500Mb/s, and p 1 has its currentBW variable equal to 300Mb/s. From that state (also depicted in Table 3, step S14), Table 3 depicts what happens when p 2 calls decrease BW(500). Processes reach a state (step S16) in which p 0 has its currentBW variable equal to 700Mb/s, p 1 has its currentBW variable equal to 300Mb/s and p 2 has its currentBW variable equal to 100Mb/s.

S1 p0 [0, 0, 0] 0 0 0 - Initial state p1 [0, 0, 0] 0 0 0 - p2 [0, 0, 0] 0 0 0 - S2 p0 [0, 0, 0] 0 800 0 - p0 calls increase BW(800) p1 calls increase BW(300) p1 [0, 0, 0] 0 300 0 - p2 [0, 0, 0] 0 0 0 - S3 p0
[0, 0, 0] 0 800 0 -p2 utoDelivers Incr, 800 p 0 p2 utoDelivers Incr, 300

p 1 p1 [0, 0, 0] 0 300 0 - p2 [800, 300, 0] 0 0 0 - S4 p0 [0, 0, 0] 0 800 1 - p0 Rreceives Ack p 2 p1 Rreceives Ack p 2 p1 [0, 0, 0] 0 300 1 - p2 [800, 300, 0] 0 0 0 - S5 p0 [0, 300, 0] 0 800 1 √ p0 utoDelivers Incr, 800 p 0 p0 utoDelivers Incr, 300 p 1 p1 [0, 0, 0] 0 300 1 - p2 [800, 300, 0] 0 0 0 - S6 p0 [0, 300, 0] 0 800 1 √ p1 Rreceives Ack p 0 p1 [0, 0, 0] 0 300 2 - p2 [800, 300, 0] 0 0 0 - S7 p0 [0, 300, 0] 0 800 1 √ p1 utoDelivers
Incr, 800 p 0 p1 utoDelivers Incr, 300 p 1 p1 [800, 300, 0] 300 0 0 -p2 [800, 300, 0] 0 0 0 -S8 p0 [800, 300, 0] 700 0 0 -p0 Rreceives Ack p 1 p1 [800, 300, 0] 300 0 0 -p2 [800, 300, 0] 0 0 0 - 1) p1 [800, 300, 0] 300 0 0 -p2 [800, 300, 0] 0 0 0 -S10 p0 [800, 300, 0] 700 0 0 -p2 calls increase BW(600) p1 [800, 300, 0] 300 0 0 -p2 [800, 300, 0] 0 600 0 -S11 p0 [800, 300, 600] 500 0 0 -p0 utoDelivers Incr, 600 p 2 p1 utoDelivers Incr, 600 p 2 p2 utoDelivers Incr, 600 p 2 p1 [800, 300, 600] 300 0 0 -p2 [800, 300, 0] 0 600 0 √ S12 p0 [800, 300, 600] 500 0 0 -p2 Rreceives Ack p 0 p1 [800, 300, 600] 300 0 0 -p2 [800, 300, 0] 0 600 1 √ S13 p0 [800, 300, 600] 500 0 0 -p2 Rreceives Ack p 1 p1 [800, 300, 600] 300 0 0 -p2 [800, 300, 600] 500 0 0 -

Performance Evaluation

In this section, we assess the performance of the FastCast protocol and compare them to that achieved by two state-of-the-art protocols: LCR [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF] and Ring-Paxos [START_REF] Marandi | Ring paxos: A high-throughput atomic broadcast protocol[END_REF]. All three protocols ensure uniform total order delivery of messages. We chose LCR because it is the only existing protocol ensuring optimal throughput [START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF]. Moreover, the choice of RingPaxos is motivated by the fact, as shown in [START_REF] Marandi | Ring paxos: A high-throughput atomic broadcast protocol[END_REF], it is the only protocol to "achieve very high throughput while providing low latency". The experiments only evaluate the failure free case because failures are expected to be very rare in the targeted environment. Note that in the faulty case, the performance of FastCast would be very similar to that of LCR provided that both protocols implement almost similar recovery algorithms. LCR and FastCast relies on the use of a perfect failure detector, whereas RingPaxos assumes a bound on the number of faulty processes.

We start by a description of the experimental setup. We then assess the bandwidth allocation protocol of FastCast, and the throughput, the response time, and the latency of FastCast, LCR and RingPaxos. Our evaluation shows that FastCast is both throughput-and latency-efficient. More precisely, throughputwise, FastCast is as efficient as LCR. Latency-wise, FastCast is more efficient than RingPaxos.

Experimental Setup

The experiments were run on a cluster comprising eight 8-core machines interconnected by a gigabit ethernet switch. Each core runs at 2.5GHz and is equipped with 16GB of RAM. Moreover, each machine runs a Linux 2.6.32 kernel. The raw bandwidth over IP between two machines (measured with Netperf [START_REF] Jones | Netperf[END_REF]) is equal to 942Mb/s. In order to ensure that the evaluation is fair, we have implemented the FastCast and LCR protocols in C++, using the same code base as the RingPaxos protocol. Finally, all the presented experiments start with a warm-up phase, followed by a phase during which performance are measured. The measurement phase lasts 5 minutes.

Bandwidth Allocation Assessment

We first assess the bandwidth allocation protocol implemented in FastCast. For that purpose, we perform the following experiment. We deploy 4 nodes that send messages of variable sizes: from 1kB to 6kB. The bandwidth requirements of nodes vary during the experiment: initially all nodes require one fourth of the total available bandwdith. After 10s, node 0 decreases its requirements, followed by node 1 at time 20s. At time 30s, node 2 increases its bandwidth requirement. Finally, at time 40s, node 0 increases its bandwidth requirement, whereas node 2 decreases them. The results are depicted in Figure 5. The X axis represents the time, whereas the Y axis is used to represent the bandwidth requirements of the 4 nodes, as well as the achieved and optimal throughput. We observe that the achieved throughput is very close to the optimal one, thus confirming that the bandwidth allocation protocol works efficiently. Moreover, we have used that experiment to assess the time it takes for a node to increase its bandwidth, i.e. the time that elapses between the moment when the node notifies other nodes that it has new bandwidth requirements and the moment when the node is allowed to increase its bandwidth. We have run that experiment multiple times and the average time required by the different nodes to increase their bandwidth was 3.8ms.

Throughput Assessment

To assess the throughput of the three protocols, we run the following benchmark: we deploy N nodes that broadcast messages at the maximum throughput they can sustain. The message size is fixed and set to 10kB, which allows reaching the best possible throughput for each studied protocol. Each process periodically computes the throughput at which it delivers messages. In this experiment, the throughput is calculated as the ratio of delivered bytes over the time elapsed since the end of the warm-up phase. The plotted throughput is the average of the values computed by each process. Figure 6 plots the throughput achieved by FastCast, LCR and RingPaxos when varying the number of nodes from 2 to 8. As reference, we plot the optimal throughput that can be achieved by (N/(N -1) times the maximum link speed of 942Mb/s). We can make several observations. First, the throughput of FastCast and LCR is very close to optimal. As mentioned in the previous section, this confirms the fact that the bandwidth allocation algorithm works efficiently. Second, the throughput of RingPaxos is almost constant (at 939Mb/s). Again, this behavior is expected: in RingPaxos, only one process at a time is allowed to send IP multicast messages. This limits the throughput that can be sustained by the protocol. For instance, with 4 nodes, FastCast and LCR are about 25% faster than RingPaxos. In a system with 2 nodes, FastCast and LCR are about 86% faster than RingPaxos. Fig. 6. Throughput as a function of the number of nodes in the system for the FastCast, LCR, and RingPaxos protocols.

Response Time Assessment

In this section, we evaluate the response time of FastCast, LCR, and RingPaxos in a system comprising 8 nodes. In this experiment, we vary the throughput at which the nodes inject new messages in the system. The size of messages that are broadcast is 10kB. During the measurement phase, for every message m it broadcasts, a sender evaluates the elapsed time between the broadcast and the delivery of m. For each protocol, we stop the curve when the injected load is higher than the throughput the protocol is able to sustain. Results are depicted in Figure 7. The X axis represents the aggregated sending throughput, whereas the Y axis represents the response time. We observe that FastCast exhibits a consistently lower response time than both LCR and RingPaxos. More precisely, FastCast achieves an up to 400% lower response time than LCR and an up to 246% lower response time than RingPaxos. This comes from the fact that both LCR and RingPaxos rely on a ring topology for sending some of the messages that are exchanged among nodes: data messages in the case of LCR, and ordering messages in the case of RingPaxos (notice that, unlike in LCR, in RingPaxos, not all processes are organized in a ring [START_REF] Marandi | Ring paxos: A high-throughput atomic broadcast protocol[END_REF]). The pipelining pattern introduced by a ring topology increases the time it takes to process each message with respect to a pure IP multicast protocol such as FastCast in which no pipelining pattern is used.

Latency Assessment

In this section, we evaluate the latency achieved by the FastCast, LCR, and RingPaxos protocols. We vary the size of the system from 2 to 8 nodes. Recall that latency is defined as the time required to complete a message broadcast when there is no contention. In order to measure the latency of the various pro- tocols, we perform the following experiment: one node in the system broadcasts 10kB messages at a very low throughput (1Mb/s). The sending node evaluates the average time that elapses between the broadcast of each message and its delivery. Results are depicted in Figure 8. The X axis represents the number of nodes, whereas the Y axis represents the latency. We observe that FastCast exhibits a consistently lower latency than both LCR and RingPaxos. More precisely, FastCast achieves an up to 465% lower latency than LCR and an up to 247% lower latency than RingPaxos. Moreover, we observe that the latency of FastCast is constant, whereas that of RingPaxos and LCR increases with the number of nodes. This again comes from the fact that both LCR and RingPaxos rely on a ring topology for sending some of the messages. The reason why the curve for RingPaxos is not linear is that in RingPaxos only a majority of nodes need to be present in the ring. For instance, RingPaxos uses the same ring size (3) for systems comprising 4 and 5 nodes, whereas in LCR, the ring size linearly increases with the number of nodes in the system.

Conclusion

We have presented FastCast, a uniform total order broadcast protocol that achieves both optimal throughput and very low latency. Unlike previous throughput-optimal protocols, FastCast does not rely on a ring topology for message dissemination. Rather, FastCast uses IP multicast, a low-level communication protocol that allows reaching multiple processes using a single message. To avoid network congestion (and thus IP multicast packet drops), FastCast implements a subprotocol in charge of dynamically computing the throughput at which processes are allowed to send IP multicast messages. We have evaluated FastCast on a cluster of 8 machines and have compared its performance to that achieved by two recent state-of-the-art protocols: LCR and RingPaxos. The evaluation shows that FastCast achieves optimal throughput and very low latency.

Currently, FastCast assumes that it is the only source of network traffic. In our future work, we plan to study extensions of FastCast to take into account background traffic. Our intuition is that a possible approach is to have all applications running on a set of nodes share the same bandwidth allocation mechanism.

Fig. 1 .

 1 Fig. 1. Multicasting messages (one sender on the left, multiple senders on the right) in a system comprising 3 nodes.

Fig. 2 .

 2 Fig. 2. Pseudo-code of the ordering mechanism.

Fig. 4 .

 4 Fig. 4. Pseudo-code of the bandwidth allocation protocol.

Fig. 5 .

 5 Fig. 5. Assessment of FastCast's bandwidth allocation protocol.

Fig. 7 .

 7 Fig. 7. Response time as a function of the aggregated sending throughput for the FastCast, LCR, and RingPaxos protocols.

Fig. 8 .

 8 Fig.8. Latency as a function of the number of nodes in the system for the FastCast, LCR, and RingPaxos protocols.

  Procedures executed by any process pi 1: upon view change(new view) do 2:Rsend Recover, pi, pendings, seqnos to all pj ∈ new view 3:Wait until received Ack Recover from all pj ∈ new view 4:Rsend End Recovery to all pj ∈ new view 5:Wait until received End Recovery from all pj ∈ new view

	6:	forceDeliver()
	7:	view ← new view
	8:	pendings[] ← ∅
	9:	seqnos[] ← ∅
	10:	acks[][] ← ∅
	11:	leader = first process in view
	12:	sn ← nextT oDeliver
	22:	toDeliver(pendings[idm])
	23:	pendings ← pendings -pendings[idm]
	24:	snT oDeliver ← seqnos[idm] + 1
	25:	for each idm ∈ keys(pending[idm]), ordered by increasing idm do
	26:	toDeliver(pendings[idm])
	27:	pendings ← pendings -pendings[idm]

13: upon Rreceive Recover, pendingsp j , seqnosp j from pj do 14:

for each [idm] ∈ pendingsp j do 15:

pendings[idm] ← pendingsp j [idm] 16: if ∃ seqnosp j [idm

] then 17: seqnos[idm] ← seqnosp j [idm] 18: Rsend Ack Recover to pj 19: procedure forceDeliver() 20: for each idm ∈ seqnos[idm], ordered by increasing sequence number do 21: if ∃ pendings[idm] and seqnos[idm] ≥ snT oDeliver then

  we depicts what happens when from

	Procedures executed by any process pi
	1: procedure initialize(initial view)
	2:	bwRequirements[] ← [0, • • • , 0]
	3:	currentBW ← 0
	4:	ongoing increase ← 0
	5:	delivered req ← f alse
	6:	acks ← 0
	7: procedure increase BW(amount)
	8:	wait until ongoing increase = 0
	9:	ongoing increase ← amount
	10:	utoBroadcast Incr, amount to all processes
	11: upon utoDeliver Incr, amount from pj = pi do
	12:	bwRequirements[pj ] ← bwRequirements[pj ] + amount
	13:	currentBW ← BW allocation()
	14:	Rsend Ack to pj
	15: upon utoDeliver Incr, amount from pi do
	16:	delivered req ← true
	17: upon Rreceive Ack from pj do
	18:	acks ← acks + 1
	19:	if acks = N -1 then
	20:	wait until delivered req = true
	21:	bwRequirements[pi] ← bwRequirements[pi] + ongoing increase
	22:	currentBW ← BW allocation()
	23:	acks ← 0
	24:	ongoing increase ← 0
	25:	delivered req ← f alse
	26: procedure decrease BW(amount)
	27:	wait until ongoing increase = 0
	28:	bwRequirements[pi] ← bwRequirements[pi] -amount
	29:	currentBW ← BW allocation()
	30:	utoBroadcast Decr, amount to all processes
	31: upon utoDeliver Decr, amount from pj = pi do
	32:	bwRequirements[pj ] ← bwRequirements[pj ] -amount
	33:	currentBW ← BW allocation()
	34: function BW allocation()
	35:	nodes ← pi and the (N-2) other iggest values in bwRequirements
	36:	availableBW ← B
	37:	do
	38:	allocated = f alse
	39:	for pj in nodes do
	40:	if bwRequirements[pj ] ≤ availableBW/size(nodes) then
	41:	nodes ← nodes -pj
	42:	availableBW ← availableBW -bwRequirements[pj ]
	43:	allocated = true
	44:	while(nodes = ∅ and allocated = true)
	45:	if pi ∈ nodes then
	46:	return availableBW/size(nodes)
	47:	return bwRequirements[pi]

Table 1 .

 1 A first example execution of the bandwidth allocation protocol.

	step	process	bwRequirements	currentBW	ongoing increase	acks	delivered req

Table 2 .

 2 A second example execution of the bandwidth allocation protocol.

	step	process	bwRequirements	currentBW	ongoing increase	acks	delivered req
	S9	p0 [800, 300, 0] 700 0 0 -	Initial state (equal to S8 in Table

Table 3 .

 3 A third example execution of the bandwidth allocation protocol.

	step	process	bwRequirements	currentBW	ongoing increase	acks	delivered req
	S14	p0 [800, 300, 600] 500 0 0 -p1 [800, 300, 600] 300 0 0 -p2 [800, 300, 600] 500 0 0 -	Initial state (equal to S13 in Table 2)
		p0 [800, 300, 600] 500 0 0 -
	S15	p1 [800, 300, 600] 300 0 0 -	p2 calls decrease BW(500)
		p2 [800, 300, 100] 100 0 0 -
		p0 [800, 300, 100] 700 0 0 -	p0 utoDelivers Decr, 500 p 2
	S16	p1 [800, 300, 100] 300 0 0 -	p1 utoDelivers Decr, 500 p 2
		p2 [800, 300, 100] 100 0 0 -	p2 utoDelivers Decr, 500 p 2

As proved in[START_REF] Guerraoui | Throughput optimal total order broadcast for cluster environments[END_REF], a total order broacast protocol can only achieve optimal throughput if all processes simultaneously broadcast messages.

Acknowledgements

We would like to thank Baptiste Lepers and the anonymous reviewers for their useful feedback on this work. Moreover, the presented work has been funded by the French ANR project called SocEDA (http://www.soceda.org) and by the EU FP7 Specific Targeted Research Project "PLAY" (http://www. play-project.eu).


Pedro Alves
email: pedro.h.alves@gmail.com

Paulo Ferreira
email: paulo.ferreira@inesc-id.pt

AnonyLikes: Anonymous Quantitative Feedback on Social Networks

Social network applications (SNAs) can have a tremendous impact in raising awareness to important controversial topics such as religion or politics. Sharing and liking are powerful tools to make some of those topics emerge to a global scale, as already witnessed in the recent Tunisian and Egyptian revolutions. However, in several countries the simple act of liking an anti-government article or video can be (and has already been) used to pursue and detain activists. Therefore, it is of utmost relevance to allow anyone to anonymously "like" any social network content (e.g. at Facebok) even in presence of malicious administrators managing the social network infrastructure. We present anonyLikes, a protocol which allows SNAs users to "like" a certain post (e.g., news, photo, video) without revealing their identity (even to the SNA itself) but still make their "like" count to the total number of "likes". This is achieved using cryptographic techniques such as homomorphic encryption and shared threshold key pairs. In addition, the protocol ensures all other desirable properties such as preventing users from "liking" a particular post more than once, while preserving anonymity. The anonyLikes protocol is fully implemented using Facebook as an example and can be easily used by developers (e.g. Facebook itself or other social network applications and infrastructures) to provide an alternative "like" button called "anonyLike".

Introduction

Social network applications (SNAs) have achieved massive popularity in recent years, with Facebook leading the way with its 900 million users 1 , but also Twitter and Linkedin both with 200 million each. 2These applications allow people all over the world to connect each other at an unprecedented scale. Although these connections are primarily being established to share media and keep in touch with friends, family and colleagues, they are also being used to raise awareness and coordinate large communities around important topics, such as the political status of some countries. For example, Egyptian activist Wael Ghonim credited Facebook with the success of the Egyptian people's uprising, in particular for its key role in organizing the most important protest on January 25 th . 3 During the revolution, hundreds of thousands of Egyptians used Facebook to post, like and share news and videos, raising global awareness about what was going on in the country.

However, that didn't prevent Wael Ghonim from being arrested for 12 days, shortly after the protest. 4 Like Wael, many activists suffered from their activities on social networks -Egypt and several other countries have been reported to track down activists on social networks 5 to the point where bloggers died while in custody for their antigovernment articles. 6We present AnonyLikes, a protocol which allows SNAs users to promote/raise awareness to certain content (news, links, photos or videos which we will refer generically as posts through the rest of the paper) without revealing their identity (even to social networks administrators). Even though social networks typically go to great length to protect the privacy of their users, they still have to abide by the legislation of each country and may be forced to reveal internal data to governmental agencies under a court order. 7 Even if that doesn't happen, there are still (less legal) ways to get access to data, either by employing hackers 8 or by tapping into internal disgruntled employees who have access to the social network database. Even under these potential attacks, AnonyLikes always guarantees the anonymity of the users who have "liked" some content. Our protocol uses cryptographic techniques (see below) to guarantee the privacy of the "like" activity (i.e., the information that an user "liked" a given post) even with access to the SNA's database.

Our interaction model is similar to the one already existent and to which users are accustomed -a "like button", which can be embedded into a blog or news site, associated with a given post along with the number of "likes" already submitted by other users. Note that we will use the term "like" for the rest of the paper as a generic verb to denote an action that increases awareness of a certain post (it could also be "share", "retweet", "reblog", etc.).

Despite similarities with the existing interaction models (in particular, Facebook) AnonyLikes is, in fact, a completely different protocol whereby messages exchanged with the social network server are encrypted in such a way that:

it is not possible to ascertain which post each user "liked"; it is possible to know how many people "liked" a certain post. This is achieved using a combination of homomorphic encryption [START_REF] Rivest | On data banks and privacy homomorphisms[END_REF] and shared threshold key pairs: [START_REF] Desmedt | Threshold cryptosystems[END_REF]:

-Users can "like" anything from an almost unlimited set of posts, i.e there is no limit to the set of posts a user can "like";

-The period during which users can "like" is unlimited, i.e.there is no closing date after which a post can no longer be "liked".

In summary, the requirements that guide the design of the anonyLikes protocol are the following:

-R1: Users should be able to "like" a given post; -R2: Only authenticated users can "like"; -R3: It must not be possible for anyone (including the social network infrastructure, e.g., facebook.com) to know a certain user "liked" a particular post; -R4: "Liking" a post must have an effect (even though not immediate) on the number of "likes" (count) of that post and that effect must be visible to everyone; -R5: It must not be possible for someone to "like" a particular post more than once; -R6: The user interaction must be similar to the one already existent in major social network applications such as Facebook and Twitter (in particular, concerning usability and performance).

Note that we cannot guarantee that the social network infrastructure servers (simply referred as SNA-server from now on) don't add fake "likes" to a given post (although this already happens today), i.e., it doesn't artificially increment the "likes" count. However, the SNA-server cannot ignore true "likes" without raising suspicion since R4 mandates that the "like" action must have an effect on "likes" count.

In summary, the contributions of this work are:

-A protocol (AnonyLikes) that allows social network users to provide quantitative feedback (e.g., "like" on Facebook) about a certain post without revealing their identity, even to the SNA-server itself. Using this protocol, social networks are still able to calculate the sum of feedback (e.g., the number of people that "liked" a given post on Facebook) while preventing multiple "likes" from the same user. -A reference implementation of the AnonyLikes protocol for Facebook "likes" that can easily be used by Facebook itself or that can serve as the basis for other social network implementations.

The remainder of this paper is organized as follows. The next section presents the AnonyLikes protocol. After that, we describe the implementation of the prototype. Section 4 presents an evaluation of the protocol regarding three aspects: Usability, Probabilistic Duplicates Detection, and Performance. Finally, Sections 5 and 6, present relevant related work and draw some conclusions, respectively.

Protocol

The anonyLikes protocol can be applied to any social network that has the concept of quantitative feedback, i.e., that features an action that increments a number associated with a post. For example, in Facebook and Tumblr, that action is "like", in Twitter is "retweet", etc. The general idea (see Figure 1) is to encrypt the "likes" with a key that is shared among the social network and a set of independent entities (e.g., NGOs) so that none of these entities alone can decrypt it. By using a special property of the encryption algorithm, the SNA-server is able to sum the number of "likes" of a given post without having to decrypt them (i.e., the sum is also encrypted). When the user wants to know how many "likes" are associated with a given post, it coordinates all the entities to jointly decrypt the sum. We now present the details of this protocol.

The anonyLikes assumes a SNA-Server S (e.g., hosted at facebook.com) and a set of Trustees T i (e.g., public national institutes, NGOs, etc.). Clients exchange encrypted messages with S and communicate with T i to decrypt such messages (in particular, the number of "likes" of a given post).

There is an initial setup process where a shared threshold key pair is generated across S and all T i . The generated public key will be published and used to encrypt all the "like" messages. Each entity (S and T i ) stores its part of the private key (also called shadow). To decrypt such messages (or, better said, the result of operations on those messages), a certain number of T i (depending on the threshold) must collaborate, i.e., S alone is not be able to decrypt them.

After the setup stage, the social network is ready to accept "like" messages. A "like" message is a tuple (post id, like), where post id is a unique identifier of the post, and like is an integer telling whether the user "liked" that post (value=1) or not (value=0). On each one of these messages, the like value is encrypted with the previously generated public key and the tuple is then sent to S. Note that, since the post id is sent in cleartext, the client cannot send only the posts the user "likes"; it has to also send posts the user didn't "like". So, every time a user "likes" a given post, the client sends not only that post id but also n random other post ids, so that S is not able to know which exact post the user "liked". S knows that the user "liked" one of those posts but is not sure which one. The post id has to be sent in cleartext to prevent duplicate "likes", as explained in the next paragraph.

Sending multiple post ids each time the user "likes" a post is crucial to satisfy requirement R5 (it must not be possible for someone to "like" a particular post more than once -see Section 1). Since the "likes" are encrypted, S has no way to know if the user already "liked" a given post (therefore satisfying requirement R3). However, it knows that the user potentially "liked" a given post -every post id sent to the SNAserver ("liked" or not "liked") is a potential "like" with probability 1/n (n is the number of post ids sent for each "like"). Based on this, S applies a probabilistic detection of multiple "likes" for the same post -it refuses post ids that has already received because there is a high probability that it is a "like" for a post the user previously "liked". Obviously, there may be false positives (i.e., S may refuse legitimate "likes") but the probability is low enough to guarantee the usability and usefulness of the system. In Section 4, we show that (being conservative) this probability is less than one collision per year for Facebook users (i.e., of all the "likes" the user does in Facebook during an year, one of them won't be successful).

Finally, the protocol allows users to see the number of "likes" of a given post, without knowing who did each individual "like". This is possible thanks to the additive homomorphic properties of an ElGamal variant known as exponential ElGamal [START_REF] Cramer | A secure and optimally efficient multiauthority election scheme[END_REF]. In exponential ElGamal, it is possible to add two encrypted messages, without having to decrypt them first, and the decryption of the encrypted sum equals the sum of the decrypted values. S applies this property by adding each encrypted "like" (remember that the "like" value is either 1 or 0) with the already existent encrypted sum of that post id (or zero if it is the first). When a user retrieves the number of "likes" of a given post, it is actually retrieving the encrypted sum associated with that post. The client is responsible for coordinating with the necessary number of Trustees (based on a pre-defined threshold) in order to decrypt that sum using their part of the private key.

Phases of the Protocol

We now detail the three phases of the protocol (setup, "liking" a post, and retrieving the number of "likes"), starting with a brief summary of the cryptographic building blocks (ElGamal cryptosystem, homomorphic encryption, threshold ElGamal, and zero knowledge proof) which are used by the protocol.

Cryptographic Building Blocks

ElGamal The anonyLikes protocol relies on the ElGamal cryptosystem [START_REF] Gamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF]. ElGamal works in the Z * p subgroup G q of order q, where p and q are large primes such that p = 2q + 1. A secret key x ∈ Z q is selected and the corresponding public key y = g x mod p is computed. A message m ∈ G q is encrypted by selecting a random integer value r ∈ Z q , and constructing the following pair (α, β) = (g r mod p, my r mod p). Decryption is computed as m = α -x β. Fig. 2. Example of a post with the associated anonyLike button and the number of (anonymized) people that "liked" that post.

Homomorphic Encryption We say that is a (⊕, ⊗)-homomorphic encryption scheme if for any instance E of the encryption scheme, given c 1 = E r1 (m 1 ) and c 2 = E r2 (m 2 ), there exists an r such that c1⊗c2 = E r (m1⊕m2). This property is crucial in the anony-Likes protocol to calculate the number of "likes" (sum) of a given post without having to decrypt individual "like" messages. The ElGamal cryptosystem satisfies this property for multiplication operations, so we need to use a variant known as exponential ElGamal [START_REF] Cramer | A secure and optimally efficient multiauthority election scheme[END_REF] that satisfies this property for additive operations, i.e. c1 * c2 = E r (m1 + m2).

Threshold ElGamal The goal of a threshold scheme for public-key encryption is to share a private key among a set of receivers such that messages can only be decrypted when a substantial set of receivers cooperate [START_REF] Desmedt | Threshold cryptosystems[END_REF]. In the anonyLikes protocol, the receivers are called Trustees. The main steps of a threshold system are: (i) a key generation step to generate the private key jointly by the receivers, and (ii) a decryption step to jointly decrypt a ciphertext without explicitly reconstructing the private key. More details about both steps applied to the ElGamal cryptosystem can be found in Cramer [START_REF] Cramer | A secure and optimally efficient multiauthority election scheme[END_REF].

Zero Knowledge Proof of Validity In the anonyLikes protocol, each "like" message contains a set of tuples (post id, E(like)), where like can be either 0 or 1. S needs to make sure that like has indeed one of those two values without revealing the exact value. This is accomplished by attaching to each tuple a proof of validity (see Cramer [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF] for more details).

Setup The setup phase occurs only once before the system is made available to the public in general. Its primary goal is to generate a keypair responsible for the encryptions/decryptions that occur in the other phases of the protocol.

S and all T i create a shared threshold ElGamal key pair ( pk , sk1 , sk2 , ..., skn ).

pk is published on S's site and S and each T i hold its part of the secret key.

"Liking" a Post This phase occurs when the user clicks the "AnonyLike" button that is associated with a given post (see Figure 2). All "likes" have to be authenticated, so if the user has not previously authenticated himself on S he will be redirected to do so, prior to submitting the "like" message. We now detail all the steps since the user clicks the "AnonyLike" button until the SNA-server responds with a successful message.

1. User U clicks the AnonyLike button associated with a given post identified by P like , using the client software (e.g., browser). 2. The client software randomly chooses n other posts P i that: (1) have occurred recently (w.r.t. the age of the post being "liked"); ( 2) are from the same topic (based on hashtags, labels and words within the post) and ( 3) are public (i.e., not confined to posts from friends). These three restrictions increase the difficulty for an attacker to guess P like from the several P i . If it simply chose posts regardless of their age or topic, the attacker could guess that the most recent or relevant P i would be the one with the "like" (and this would be correct in the vast majority of cases). Also, choosing only posts from friends would hugely reduce the set of posts from which to draw the random ones so we use only public posts (which is usually the case for the political/ideological posts that motivated this article). 3. The client software creates a message M containing the tuple (P like , E pk (1)) and a set of n tuples (P i , E pk (0)), 1 <= i <= n. This means the software encrypts "1" for the post the user "likes" and "0" for the others. The position of the P like tuple in the message is random (its index is obtained from a random number generator). 4. The client software sends this message to S (remember that U has already been authenticated in S) plus a set of proofs P roof i (one for each tuple) that will be used to verify that they contain valid "like" values. 5. S uses P roof i to verify that the "like" value for each post is either 0 or 1 (without having to decrypt it). 6. S updates the vector of potencial "likes" of this user V u = (P 0 , ..., P n ). This vector contains all P i that ever came in a message associated with this user. If any P i contained in the message already exists in V u , the SNA-server S returns an error. This is to probabilistically prevent duplicated "likes" from the same user for the same post. 7. S updates its LikesStats table (P i , E pk (num likes)) for every P i in the message using the additive property of homomorphic encryption, without having to decrypt the tuples in the message. This table stores the total number of "likes" of every post in the system, encrypted by pk . M can now be discarded. 8. S responds to the client software with a success message.

Note that, steps 5 and 6 prevent the submission of multiple "likes" for the same post (requirement R5). In addition, step 7 guarantees that the "like" has an effect on the number of "likes" of the associated post while still preventing S from knowing which particular post the user "liked".

Retrieving the Number of "Likes" This phase is responsible for retrieving the number of users that already "liked" a given post, as shown in Figure 2. Usually, this is calculated by the SNA-server but, in anonyLikes, the SNA-server has no way of knowing this number since it is encrypted with a shared key that is distributed among a set of trustees (generated on the previously mentioned setup phase). Therefore, the client software assumes the role of coordinating with the Trustees to decrypt that number.

1. The client software asks S for the number of "likes" of a given post P i ; 2. S searches its LikesStats table for P i and gets the corresponding E pk (num likes); 3. S partially decrypts the num likes -D sk1 (E pk (num likes)) and returns this to the client; 4. The client software sends D sk1 (E pk (num likes)) to several T i (previously chosen by the user or random) until it is fully decrypted. Supposing we had 2 Trustees (T 1 and T 2 ), the final decrypted num likes would be the result of

D sk T 2 (D sk T 1 (D sk SN A-Server (E pk (num likes)))) 5.
Finally, the client software shows the user the number of "likes".

Implementation

To evaluate the anonyLikes protocol, we developed three components: the SNA-server component, the trustee component and the client component. We used these components to implement a web application that provides an interface showing several random posts from Facebook (10 in the current implementation) along with an anonylikes button and the anonymized number of people that "liked" each one of such posts.

Due to the non-anonymous nature of Facebook, it is not possible to implement this protocol on top of their API. 9 For example, to use the API for submitting a "like", the application has to provide the user who is "liking", therefore preventing any kind of anonymization. Nothe that, using the same (fake) user for all "likes" doesn't work because Facebook prevents more than one "like" from the same user. Our SNA-server component is therefore a simplified replica of Facebook with some adaptations to allow the implementation of the anonyLikes protocol. This component can be the basis for adaptations implemented by Facebook itself, should it decide to use the anonyLikes protocol in the future.

Table 1 shows the responsibilities of each component. Note that the encryption/decryption operations are all performed by the client component. We now look into detail on each of such components.

SNA-Server Component

The SNA-server component is responsible for: (i) coordinating the distributed generation of the threshold shared key, (ii) receiving encrypted "like" messages, and (iii) providing the encrypted sum of "likes" that will be used to show how many people "liked" a given post. It is implemented as a Python/Django application and its source code is fully available at https://bitbucket.org/anonymousJoe/anonylikes. AnonyLikes reuses some code that was adapted from the Helios system [START_REF] Adida | Helios: Web-based open-audit voting[END_REF] as it provides the implementation of some of the cryptography functions needed (and the code is open-source). 10 .

The SNA-server connects to a MySQL database with 3 tables: (i) PublicKey -contains the public key used to encrypt "likes"; (ii) LikesStats -contains tuples (post id, encrypted num likes), and (iii) PotentialLikesUser -contains all the post ids that each user has potentially "liked".

Comp.

Responsibilities

Impl. Several actions in the SNA-server must be previously authenticated. We delegate the authentication on Facebook using their OAuth implementation. 11 If the user is not already authenticated in our SNA-server, he is redirected to Facebook where he is asked if he wants to login into AnonyLikes and provide his basic information and email (see Figure 3).

SNA-Server

Generation of the Shared Key

The generation of the shared key among all the Trustees is partially executed in the browser and partially executed in the SNA-server. The SNAserver starts by generating the public key and its part of the secret key. Then, each Trustee opens the Trustee setup page using a browser to locally generate its part of the secret key. This generation is performed in the browser using a Javascript implementation of the ElGamal cryptosystem. Each Trustee stores locally the generated secret key which is then cleared from the browser's memory. Throughout the whole process, the secret key never leaves the Trustee's computer.

Receiving Encrypted "Likes" The SNA-server provides a REST endpoint to receive encrypted "like" messages. Although programmers can use this endpoint directly, we also provide an embeddable html/javascript that can easily be included on any site to add an "AnonyLike" button (see Figure 2). In this case, all the encryption and communication is automatically handled by the embedded javascript code.

This endpoint verifies that all the encrypted "likes" contained in the message are valid "likes" (i.e., contain the value 0 or 1) using a Zero Knowledge Proof Verification algorithm (already mentioned in the Section 2). Then, for each one, it adds it (using ELGamal homomorphic additive properties) to the existing number of "likes" associated with that post using the LikesStats table. Finally, it updates the PotentialLikesUser table with all the post ids contained in the message.

Providing the Encrypted Sum of "Likes" The SNA-server provides a REST endpoint that responds with the number of "likes" of a given post. This is a simple query to the LikesStats table. Since the SNA-server has one part of the shared secret key, it just partially decrypts the number of "likes" before returning it to the client.

Trustee Component

The trustee component is responsible for storing its part of the shared secret key and, based on that, providing the decryption factor through a REST endpoint. It is implemented as a Bottle server (very lightweight application server that runs Python) that is easily installed on any hosting provider. This component should be installed by each Trustee on a server of his choice. The url of such servers must be made public, so that clients can choose among all the Trustees the ones that will be contacted to get the decryption factor.

Client Component

The client component is where the encryption/decryption takes place using a Javascript implementation of the ElGamal cryptosystem. Since the Javascript technology is too slow for certain heavy operations such as generating randomness and modular exponentiation, Java is utilized for such computation, using an applet running in the browser.

We now detail two important aspects of the Client component implementation: how to embed the "anonyLike" button, and how to retrieve random posts to go along the real post (i.e the one "liked"). Embedding the "anonyLike" Button The client component consists of a javascript file (anonyLikes.js) and several cryptographic libraries (e.g., elgamal.js). For convenience, programmers only have to import anonyLikes.js as depicted in Figure 4 and all the required cryptographic libraries are automatically loaded. Then, programmers have to insert HTML code similar to Figure 5 in the place where they want the "anonyLike" button to show up. anonyLikes.js inserts html code inside that < div > to show the button and the number of people that already "liked" that post. This is very similar to how the original Facebook "like" button is embedded, so it is easy to include anonyLikes on any site.

Retrieving Random Posts Another important aspect of the Client component implementation is obtaining n random recent posts to go along the "liked" post (recall that the message sent to the SNA-server contains the post id the user "liked" plus n random post ids the user didn't "like"). This operation is performed by the browser using AJAX calls to the Facebook's API. Since Facebook's API only provides a service to search for posts, we get random posts by issuing random queries and getting the first result. This operation (obtaining n random posts) is executed in the background as soon as the page loads to minimize the time spent after clicking the "anonyLike" button (see next section). The user usually clicks the "anonyLike" button after reading/watching the post, which takes sufficient time for the background job to finish retrieving n random posts.

Evaluation

In this section, we present the response to the following questions that are crucial to the success of anonyLikes:

-Usability -Can we satisfy requirement R6 (The user interaction must be similar to the one already existent in major social network applications such as facebook and twitter)? -Duplicates Detection -Does our probabilistic duplicates detection mechanism (necessary for requirement R5) affect the user experience? -Performance -Is the performance of our prototype adequate to user expectations (requirement R6)?

Total users 1.060 billion Average daily "likes" 2.7 billion Average daily "likes" per user 2.5 "likes" Number of "likes" per year 912 "likes" Total number of location-tagged posts 17 billion Table 2. Some statistics on Facebook usage

Usability

The AnonyLikes behavior is very similar to the original Facebook "like" behavior from the user's perspective. As can be seen in Figure 2, the look of both the button and number of users who already "liked" is very similar to the original one. From the programmer's perspective it is also very similar as programmers only need to import one javascript library (see Figure 4) and define the placeholder where the button will show up (see Figure 5).

So, from a usability point of view, the anonyLikes functionality is as easy as the original Facebook "like" functionality (which is already used by millions).

Probabilistic Duplicates Detection

The anonyLikes protocol relies on the assumption that it is highly unlikely that a user will "like" one of the random posts that is sent along the "liked" one. This assumption is the basis for duplicate "like" detection: if the user "likes" a post that he has already potentially "liked", the SNA-server will not accept that action because it will assume that the user is "liking" the same post twice.

The actual probability of such occurrence is calculated taking into account three variables: M being the total number of posts on Facebook (the universe from which to grab the random posts); n being the number of post ids that are sent within each message (n -1 random posts plus the "liked" one), and L being the number of "like" messages the user sends per year. Thus, the probability of getting a collision per year is:

P r collision = Ln M (1)
In Table 2 we show some stats on Facebook. 12 Unfortunately, the total number of posts is not available (only the total number of location-tagged posts) so we will assume 17 billion as the total number of posts which is clearly a conservative assumption, given that many posts are still not location-tagged. We are also making the very conservative assumption the total number of posts is constant per year.

With these numbers, we can now calculate the P r collision (per year), using n = 20:

P r collision = 912 * 20 17.000.000 = 0, 1% We can see that, even with our very conservative assumptions (we believe that this probability is much lower), the user will have approx. one collision per year (0,1% of 912 posts). We believe that this is an acceptable collision rate; obviously, developers can use higher n values to further decrease the number of collisions, although doing so will also impact the performance of the application as explained in the next section.

Performance

There are three steps in the anonyLikes protocol that may take long enough to affect the usability: (i) retrieving n random posts; (ii) encrypting the message with the "likes", and (iii) decrypting the number of "likes". Their duration is related to CPU consumption and time spent on network calls. We measured each of these steps.

Retrieving n Random Posts To retrieve n random posts we issue n AJAX calls to Facebook's search API. We experimented with two different approaches: (i) sequentialwe make (synchronously) AJAX calls sequentially, and (ii) parallel -we make all AJAX calls in parallel and wait until all of them finish. Using the Chrome browser connected to the Internet through a regular domestic 6 Mb/s Cable connection (a common scenario), we achieved the results shown in Table 3.

As expected, the parallel approach is much faster as the browser establishes multiple connections with Facebook. However, per the HTTP specification, browsers put a cap on the maximum number of connections to the same host (this cap is browser dependent). In Chrome (the browser that was used for these tests) the cap is 6 connections and that is the reason why the time to get 4 random posts is equal to the time needed to get 6 random posts.

Even if we set n to be 18, and given the fact that we start fetching random posts as soon as a page loads, we find 5.4 seconds to be a reasonable time that doesn't affect the usability because the user will generally take longer to read the page content before clicking the "anonyLike" button.

Encrypting "Like" Messages To measure the time spent on the ElGamal encryption algorithm, we used both Chrome and Firefox browsers running on a Intel Core i7 Processor (4 cores) at 2.2Ghz (Windows 8). We experimented several values for n (number

Operation Chrome Firefox

Encrypt "likes" (n = 6) 1366 1324

Encrypt "likes" (n = 12) 2742 2461

Encrypt "likes" (n = 20) 4584 3968 Table 4. Average time spent encrypting the number of "likes" (ms)

Operation

Avg. time (ms)

Getting encrypted num of "likes" from SNA-server 19

Getting decryption factor from one trustee 79

Decryption in the browser (Javascript) 30

Total (with three trustees) 286 Table 5. Average time spent on getting and decrypting the number of "likes" of random posts that go along the "liked" post) since this affects directly the encryption time.

We can see in Table 4 that, although the ElGamal encryption is a heavy operation, it consumes an acceptable amount of time. We can also see that Firefox is slightly faster than Chrome but the difference is very small. To improve the user experience, we use a similar technique to what we used for retrieving random posts (see previous subsection): start encrypting the "like" as soon as the page loads so that when the user clicks the button it is (hopefully) already encrypted and the user only has to wait for the SNA-server to respond. If the user takes longer than 10 secs to read the page, it is long enough to hide the 5.4 secs retrieving random posts (as shown in previous section) plus 4 secs encrypting; thus, the "like" will have already been encrypted before the user reads the page; otherwise he will have to wait a few seconds (during which a progress dialog is shown).

Decrypting the Number of "Likes" Decrypting the number of "likes" involves three steps: (i) getting the encrypted number of "likes" from the SNA-server; (ii) getting the decryption factors from each trustee; (iii) use the decryption factors to decrypt the number of "likes".

We can see that the time spent is split between network calls and CPU consumption. To measure this operation, we used a Chrome browser running on a Intel Core i7 Processor (4 cores) at 2.2Ghz (Windows 8). We used three Trustees and both the SNA-Server and the Trustees were in the same machine as the browser (localhost). Since we cannot control the real network bandwidth that will be available to anonyLikes clients, we measured this operation on the localhost. This way, we could understand how long the SNA-server takes to respond with the encrypted number of "likes" (step i), and how long each trustee takes to respond with the decryption factor (step ii). Table 5 shows the results. We can see that the whole operation is very fast (almost unnoticeable by the user) with most time spent in getting the decryption factors from each trustee. Obviously, the more trustees needed to decrypt the message, the longer it will take.

We believe that three trustees is a reasonable number of trustees in a real-world scenario (regarding the risk of collusion) but there is nothing in anonyLikes preventing any other number of trustees. We have performed the same performance tests (as above) with five and seven trustees and the whole operation is very fast as well (424 ms and 552 ms, respectively).

Related Work

AnonyLikes is motivated by the recent use of SNAs as a vehicle for activism and can be related to previous work done in the area of electronic voting (considering a vote to be similar to a "like"). Therefore, we present related work pertaining both areas.

Activism and Privacy on Social Networks

The role of social networks during major political transitions such as the ones witnessed in Tunisia, Egypt and Iran have raised interest on the research community in recent years [START_REF] Lotan | The Revolutions Were Tweeted: Information Flows During the 2011 Tunisian and Egyptian Revolutions[END_REF][START_REF] Al-Ani | The Egyptian blogosphere: a counter-narrative of the revolution[END_REF][START_REF] Wulf | On the ground'in Sidi Bouzid: investigating social media use during the tunisian revolution[END_REF]. For example, the series of uprisings transforming the Arab world (the so-called "Arab Spring") following the Tunisian revolution in January 2011 made extensive use of SNAs coupled with mobile technology enabling citizens to create communities bounded together by a common goal [START_REF] Olaore | Politexting: Using Mobile Technology to Connect the Unconnected and Expanding the Scope of Political Communication[END_REF]. Also, some studies have shown the impact of SNAs on civic activism (activism not targeted towards a government) such as the Mexican Drug War [START_REF] Monroy-Hernández | The new war correspondents: he rise of civic media curation in urban warfare[END_REF]. These forms of activism all share concerns regarding the privacy of the people involved, since the targeted entity (e.g., government, drug cartel) can repress them by arresting, torturing and even killing.

To prevent these forms of repression, activists have to take special measures to protect themselves. They use pseudonyms instead of real names on their SNA accounts [START_REF] Wulf | On the ground'in Sidi Bouzid: investigating social media use during the tunisian revolution[END_REF]. However, using pseudonyms has several disadvantages: (1) people don't trust pseudonyms as much as real names; (2) pseudonyms can be used by the government to post misleading activist content; [START_REF] Benaloh | Verifiable secret-ballot elections[END_REF] given enough history, it is possible to associate pseudonyms with real identities [START_REF] Beresford | Location privacy in pervasive computing[END_REF].

More experienced users also hide their IP address (which can be used to identify them by their location) when making connections with SNAs using proxy servers or public hotspots [START_REF] Wulf | On the ground'in Sidi Bouzid: investigating social media use during the tunisian revolution[END_REF]. However, this technique relies on technological know-how that the majority of the users don't have. One interesting (and effective) measure taken by the authorities to suppress and obstruct the information flow between local internet activists is to reduce the speed of data transfer on the local ISP (Internet Service Provider) thus increasing the time to upload video materials to Facebook accounts. Activists get around this restriction by sending the material abroad via email in low resolution to be uploaded from there.

The use of pseudonyms raises a fundamental question: "can I trust this person?". For example, Monroy-Hernandez [START_REF] Monroy-Hernández | The new war correspondents: he rise of civic media curation in urban warfare[END_REF] presents the difficulty on asserting the credibility of information as one of the main conclusions of his work on the role of SNAs in Mexican Drug War. One important technique outlined in his work is to test reproducibility -if the same fact is present in posts coming from multiple disparate sources, than it must be true. Based on this, some people have created special well-known Facebook accounts to which everyone can send messages. If a lot of messages contain the same fact, that fact is published on this account.

The anonyLikes protocol is designed to protect the privacy of content "likers" and not so much the content creators. However, it can also help anonymized (through pseudonyms) content creators to get credibility through the amount of quantitative feedback their posts receive. Although not guaranteed, a post "liked" by thousands of users is more credible than a post "liked" by only a few. By protecting the privacy of the "likers", this effect may be more visible on these environments.

Electronic Voting

Electronic voting has been a research topic for over 25 years [START_REF] Benaloh | Verifiable secret-ballot elections[END_REF][START_REF] Chaum | Elections with unconditionally-secret ballots and disruption equivalent to breaking RSA[END_REF]. Today, there is a consensus on the minimum set of properties that these systems should satisfy [START_REF] Joaquim | EVIV: An end-to-end verifiable Internet voting system[END_REF]:

-Accuracy: (1) it is not possible for a vote to be altered, (2) it is not possible for a validated vote to be eliminated from the final tally, and (3) it is not possible for an invalid vote to be counted in the final tally. -Democracy: (1) it allows only eligible voters to vote, and (2) it ensures that eligible voters vote only once. -Privacy: (1) neither authorities nor anyone else can link any ballot to the voter who cast it, and (2) no voter can prove that he voted in a particular way. -Verifiability: anyone can independently verify that all votes have been counted correctly.

Note that when compared to our scenario of supporting anonymous "likes" in social networks, there are some relevant differences: i) users can "like" anything from an almost unlimited set of posts while in elections there is a small limited set of candidates from which to choose from, and ii) the period during which users can "like" is unlimited, while in an election there is not a point in time when the election is closed and the number of votes revealed; this is also related to the fact that, while on elections it is not possible to know intermediary results (i.e., to know the current vote count before the voting period ends) in SNAs it is possible (and desirable) to know the current number of "likes" at any time.

Regarding the accuracy property, the anonyLikes protocol cannot ensure that it is not possible to inject fake "likes". However, it ensures that a "like" cannot be transformed into a "non-like" (since what is stored is the number of "likes" and not the individual "like"). AnonyLikes also satisfies the democracy and privacy properties but does not satisfy the verifiability property. However, since users expect to see an immediate increase on the number of "likes" after their action, it would be very difficult to alter (adding or decreasing) the "likes" count without raising suspicions. This derives from the fact that in anonyLikes, the effect of a "like" must be visible to everyone (requirement R4).

Voting protocols can be categorized into three main categories accordingly to their cryptographic primitives: mixnets [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF][START_REF] Juels | Coercion-resistant electronic elections[END_REF], blind signatures [START_REF] Fujioka | A practical secret voting scheme for large scale elections[END_REF][START_REF] Joaquim | EVIV: An end-to-end verifiable Internet voting system[END_REF] and homomorphic encryption [START_REF] Benaloh | Verifiable secret-ballot elections[END_REF][START_REF] Cramer | A secure and optimally efficient multiauthority election scheme[END_REF].

Mixnets create a robust anonymous channel by having encrypted votes going through a collection of servers whose task is to shuffle them. To ensure that mix-servers do not drop or replace votes, the servers must provide proofs of correct operation. One example of mixnets applied to elections is the scheme proposed by Lee [START_REF] Lee | Providing receipt-freeness in mixnet-based voting protocols[END_REF] consisting on four steps. First, each voter prepares a first ballot by encrypting his vote. The ballot is then sent to a tamper-resistant randomizer (TRR) for randomization. Second, the TRR randomizes the first ballot with re-encryption to produce a final ballot. Third, the TRR also produces a Designated Verifier Re-encryption Proof (DVRP) to prove the correctness of re-encryption to the voter. The final ballot and the DVRP are then sent to the voter. Finally, the voter checks the DVRP, then signs and submits the final ballot if the check is accepted. A general criticism of mixnets is that the proofs of correction can be complex, cumbersome and inefficient [START_REF] Fujioka | A practical secret voting scheme for large scale elections[END_REF].

Blind signatures [START_REF] Chaum | Blind signatures for untraceable payments[END_REF] are a class of digital signatures where a message gets digitally signed without giving any knowledge about the message to the signer. This is similar to putting a document and a sheet of carbon paper in a sealed envelope that somebody signs on the outside. After removing the envelope we get the signed document. Applying this technique to electronic elections, voters obtain a blind signature on their ballot from an administrator which is then submitted to a voting bulletin board. The bulletin board will only accept votes signed by the administrator. This protocol has the advantages of simplicity and low computational cost. The problem is that the submission of votes to the bulletin board must use an anonymous channel which is hard to achieve. Frequently, this anonymous channel is implemented using mixnets but if a mixnet is available a blind signature is not required anymore.

Regarding SNAs, blind signatures have been used to design a privacy-enhanced variant of Twitter, where the content, hashtags and follower interests are encrypted and thus not visible to the Twitter server [START_REF] Cristofaro | Hummingbird: Privacy at the time of twitter[END_REF]. However, this mechanism doesn't provide anonymous quantitative feedback (e.g., number of retweets).

In a homomorphic encryption-based [START_REF] Rivest | On data banks and privacy homomorphisms[END_REF] voting scheme, votes are added while encrypted, so no individual vote ever needs to be revealed. In order to ensure that the private decryption key of the election is not used to decrypt an individual vote, a threshold encryption scheme must be applied to distribute the key among several authorities in such a way that multiple authorities have to combine their shares in order to use it. Although computationally expensive, this scheme has the big advantage of not requiring an anonymous channel. In fact, voters may openly authenticate themselves to the voting servers. Since the anonyLikes protocol is to be used in large-scale through the Internet channel (increasing the complexity of creating an anonymous channel), we chose homomorphic encryption as the underlying scheme for the anonyLikes protocol. Homomorphic encryption has already been proposed as privacy-preserving mechanism for SNAs. For example, Domingo-Ferrer [START_REF] Domingo-Ferrer | Privacy homomorphisms for social networks with private relationships[END_REF] proposes a system that uses homomorphic encryption to preserve the privacy of social network relationships when accessing a resource. It has also been used to preserve privacy when finding friends within a certain geographical distance [START_REF] Dong | Secure friend discovery in mobile social networks[END_REF] and matching personal profiles [START_REF] Li | FindU: Privacy-preserving personal profile matching in mobile social networks[END_REF] among others.

To the best of our knowledge, anonyLikes is the first protocol to apply homomorphic encryption (or any cryptographic technique whatsoever) to quantitative feedback in social networks.

Conclusions

Quantitative feedback on SNAs has been shown to have profound impact on several forms of activism, by raising awareness and giving voice to important and sensitive topics in environments that otherwise constrain freedom of speech. Examples of such environments are countries with authoritarian governments and cities controlled by drug cartels. In these environments, people are afraid to use SNAs to promote their causes as they can be subject to retaliations from the targeted entities.

In this paper, we propose anonyLikes, a protocol that enables SNAs users to give quantitative feedback without revealing their identity, even to the social network infrastructure itself. This protocol employs strong cryptographic techniques (homomorphic encryption, shared threshold key pairs) to guarantee the privacy of the users. In particular, what is stored on the SNA-server is not individual "likes" but rather the count of "likes" on any given post. Moreover, that count is encrypted in such a way that several entities (trustees) must collaborate to decrypt it (i.e., it is not possible for a single entity to decrypt it).

We are able to probabilistically prevent duplicated "likes" without breaking user's privacy by mixing the real "like" with several fake "likes" (i.e. by sending several post ids for which the SNA-server doesn't know if they have been "liked" or not). This effectively prevents duplicated "likes" but can wrongly prevent a legitimate "like" although this happens only once per year on average. We believe we have achieved an acceptable tradeoff between privacy and usability.

We have implemented the anonyLikes protocol within a Facebook replica, using an interaction model very similar to Facebook: developers can easily embed an "anony-Like" button next to any content (blog post, video, etc.). The same mechanism also displays the current number of "likes" of that post. This implementation is publicly available and can be used by any SNA developer wishing to support privacy-preserving quantitative feedback.

Finally, we evaluated the performance of the system and found that it can be implemented today without breaking user expectations for this kind of applications. Moreover, since the performance is tied to CPU speed, it will tend to improve in the upcoming years with advances in processor technology.

Fig. 1 .

 1 Fig. 1. The 3 steps of the AnonyLikes protocol.

Fig. 3 .

 3 Fig. 3. Users login into AnonyLikes through Facebook

Fig. 4 .

 4 Fig. 4. How to include the anonylikes javascript library and all its dependencies

Fig. 5 .

 5 Fig. 5. How to embed the anonylikes button

Table 1 .

 1 Responsibilities of each anonyLikes component

		Generate public key	Django/
		Coordinate generation of shared secret key Python
		Store secret key (SNA-server part)
		Receive encrypted "Likes"
		Provide encrypted sum of "Likes"
	Trustee	Store secret key (trustee part)	Bottle/
		Provide decrypting factor	Python
	Client	Retrieve random posts	Browser/
		Encrypt "likes"	Javascript
		Send encrypted "Likes"
		Receive encrypted sum of "Likes"
		Get decryption factors
		Decrypt sum of "Likes"

Table 3 .

 3 Average time spent on getting random posts from Facebook

	Type	n Avg. Time (s)
	Sequential	4 6	6.5 8.5
		12	18.3
		18	26.9
	Parallel	4 6	2.0 2.0
		12	3.8
		18	5.4

http://www.statisticbrain.com/facebook-statistics/

http://blog.linkedin.com/2013/01/09/linkedin-200-million/, http://mashable.com/2012/12/18/twitter-200-million-active-users/

http://www.huffingtonpost.com/2011/02/11/egypt-facebook-revolution-waelghonim n 822078.html.

[START_REF] Beresford | Location privacy in pervasive computing[END_REF] http://www.huffingtonpost.com/2011/02/07/wael-ghonim-google-exec-egyptprotests n 819438.

html 5 http://readwrite.com/2011/06/15/the arab spring a status

report 6 http://readwrite.com/2011/04/12/bahraini blogger dies in

custody 7 http://www.theregister.co.uk/2012/06/11/woman wins landmark trolling case against

facebook/ 8 http://www.guardian.co.uk/media/2013/jan/31/new-york-times-hacking-china-cybercrime

http://developers.facebook.com/docs/reference/api/publishing/

Available at https://github.com/benadida/helios-server

http://developers.facebook.com/docs/concepts/login/

http://expandedramblings.com/index.php/by-the-numbers-17-amazing-facebook-stats/

Acknowledgments

This work was partially supported by national funds through FCT -Fundac ¸ão para a Ciência e a Tecnologia, under projects Pest-OE/EEI/LA0021/2013 and PTDC/EIA-EIA/113993/2009.