Permissioned blockchains are supported by identified but individually untrustworthy nodes, collectively maintaining a replicated ledger whose content is trusted. The Hyperledger Fabric permissioned blockchain system targets high-throughput transaction processing. Fabric uses a set of nodes tasked with the ordering of transactions using consensus. Additional peers endorse and validate transactions, and maintain a copy of the ledger. The ability to quickly disseminate new transaction blocks from ordering nodes to all peers is critical for both performance and consistency. Broadcast is handled by a gossip protocol, using randomized exchanges of blocks between peers.We show that the current implementation of gossip in Fabric leads to heavy tail distributions of block propagation latencies, impacting performance, consistency, and fairness. We contribute a novel design for gossip in Fabric that simultaneously optimizes propagation time, tail latency and bandwidth consumption. Using a 100-node cluster, we show that our enhanced gossip allows the dissemination of blocks to all peers more than 10 times faster than with the original implementation, while decreasing the overall network bandwidth consumption by more than 40%. With a high throughput and concurrent application, this results in 17% to 36% fewer invalidated transactions for different block sizes.

We study convolutional LDPC codes over the binary erasure channel for immutable distributed storage systems. These codes allow the archival of data objects in a sequential fashion on an increasing number of storage nodes as they arrive in the system, as well as fast repair using a simple message passing decoder. We further target systematic codes, high code rates and low locality, which are paramount in this setting. We describe a family of codes that split each archived data object in s blocks, entangle them with t = s + p blocks already archived, and generate p parity blocks per archived data object. We carefully choose the parity-check matrix and the blocks already archived to maximize the repair capability of the resulting codes, and describe the best constructions for 1 ≤ s ≤ 5 and p = 2. A Markov analysis shows that for the same storage overhead, our codes are orders of magnitude more reliable than state-of-the-art Reed-Solomon and locally repairable codes.

Long-term archival storage systems must protect data from powerful attackers that might try to corrupt or censor (part of) the documents. They must also protect the corresponding metadata information, which is essential to maintain and rebuild the stored data. In this practical experience report, we present metablock, a metadata protection system leveraging the Ethereum distributed ledger. We combine metablock with an existing secure long-term data archival system to provide a scalable design that allows external auditing, data validation and efficient data repair. We reflect on our experiences in using a blockchain for metadata protection, with the goal of providing valuable insights and lessons for developers of such secure systems, by highlighting the potential and limitations of the approach. Our prototype is available at https://github.com/ArnaudLhutereau/mb.

File systems have long benefited from hardware acceleration to improve their performance. In order to leverage such hardware capabilities, file systems rely on direct and trusted support from the underlying operating system. However, this assumes that the OS and the associated kernel drivers, which access the accelerators, are trustworthy. The recent introduction of the Intel software guard extensions (SGX) instruction set allows application developers to lift part of these assumptions, in conjunction with the widespread availability of these new extensions in mass-market CPUs. With SGX, programmers can design secure applications under a stronger adversarial model, such as a compromised OS or kernel module. Code executes inside enclaves and is protected from privileged processes, including the OS itself. This paper presents SGX-FS, a new user-space file system that leverages SGX data sealing capabilities for secure in-memory and persistent storage. It combines the FUSE framework with SGX to securely protect user data. In particular, SGX-FS efficiently encrypts and decrypts the application data within the enclaves. We fully implement an open-source SGX-FS prototype and evaluate its performance by means of a representative set of nano-and micro-benchmarks.

Users entrust an increasing amount of data to online cloud systems for archival purposes. Existing storage systems designed to preserve user data unaltered for decades do not, however, provide strong security guarantees - at least at a reasonable cost. This paper introduces RECAST, an anti-censorship data archival system based on random data entanglement. Documents are mixed together using an entanglement scheme that exploits erasure codes for secure and tamper-proof long-term archival. Data is intertwined in such a way that it becomes virtually impossible to delete a specific document that has been stored long enough in the system, without also erasing a substantial fraction of the whole archive, which requires a very powerful adversary and openly exposes the attack. We validate RECAST entanglement approach via simulations and we present and evaluate a full-fledged prototype deployed in a local cluster. In one of our settings, we show that RECAST, configured with the same storage overhead as triple replication, can withstand 10% of storage node failures without any data loss. Furthermore, we estimate that the effort required from a powerful censor to delete a specific target document is two orders of magnitude larger than for triple replication.

Mobile Ad-hoc Networks (MANETs) use limited-range wireless communications and are thus exposed to partitions when nodes fail or move out of reach of each other. Detecting partitions in MANETs is unfortunately a nontrivial task due to their inherently decentralized design and limited resources such as power or bandwidth. In this paper, we propose a novel and fully decentralized approach to detect partitions (and other large membership changes) in MANETs that is both accurate and resource efficient. We monitor the current composition of a MANET using the lightweight aggregation of compact membership-encoding filters. Changes in these filters allow us to infer the likelihood of a partition with a quantifiable level of confidence. We first present an analysis of our approach, and show that it can detect close to 100% of partitions under realistic settings, while at the same time being robust to false positives due to churn or dropped packets. We perform a series of simulations that compare against alternative approaches and confirm our theoretical results, including above 90% accurate detection even under a 40% message loss rate.

We present STeP-archives, a novel and practical data archival architecture, where an attacker who wants to censor or tamper with a data object must cause obvious collateral damage to a large number of other objects in the system. We use maximum distance separable erasure codes to entangle unrelated data blocks and provide redundancy against storage failures, which results in an archive with constant time read-write operations. We show a tradeoff for the attacker between attack complexity, irrecoverability, and collateral damage. We also show that the problem is asymmetric between attackers and defenders; while a defender can efficiently recover from imperfect attacks, an attacker must solve an NP-hard problem to find a perfect (irrecoverable) attack that minimizes collateral damage to other data objects, or even approximate its size. We then study efficient sample-heuristic attack algorithms that lead to irrecoverable but large damage and demonstrate how some strategies and parameter choices allow to resist these sample attacks. Finally, we provide empirical evidence that an attacker who wants to irrecoverably tamper with a document archived long enough must destroy a constant fraction of the archive.

We consider the problem of reliable gossip/epidemic dissemination in a network of n processes using push and pull algorithms. We generalize the random phone call model so that processes can refuse to push a rumor or answer pull requests. With this relaxation, we show that it is possible to disseminate a rumor to all processes with high probability using Theta(ln n) rounds of communication and only n+O(n / ln n) messages, both of which are optimal and achievable with push-pull and pull-only algorithms. Our algorithms are strikingly simple, address-oblivious and thus fully distributed. This contradicts a well-known result of Karp et al. stating that any address-oblivious algorithm requires Omega(n ln ln n) messages. We also develop precise estimates of the number of rounds required in the push and pull phases of our algorithms to guarantee dissemination to all processes with a certain probability. For the push phase, we focus on a practical infect upon contagion approach that balances the load evenly across all processes. As an example, our push-pull algorithm requires 17 rounds to disseminate a rumor to all processes with probability 1 - 10^-100 in a network of one million processes with a communication overhead of only 0.4%.

The exponential growth of data produced, the ever faster and ubiquitous connectivity, and the collaborative processing tools lead to a clear shift of data stores from local servers to the cloud. This migration occurring across different application domains and types of users---individual or corporate---raises two immediate challenges. First, out-sourcing data introduces security risks, hence protection mechanisms must be put in place to provide guarantees such as privacy, confidentiality and integrity. Second, there is no "one-size-fits-all" solution that would provide the right level of safety or performance for all applications and users, and it is therefore necessary to provide mechanisms that can be tailored to the various deployment scenarios.

Content-based publish/subscribe provides a loosely-coupled and expressive form of communication for large-scale distributed systems. Confidentiality is a major challenge for publish/subscribe middleware deployed over multiple administrative domains. Encrypted matching allows confidentiality-preserving content-based filtering but has high performance overheads. It may also prevent the use of classical optimizations based on subscriptions containment. We propose a support mechanism that reduces the cost of encrypted matching, in the form of a prefiltering operator using Bloom filters and simple randomization techniques. This operator greatly reduces the amount of encrypted subscriptions that must be matched against incoming encrypted publications. It leverages subscription containment information when available, but also ensures that containment confidentiality is preserved otherwise. We propose containment obfuscation techniques and provide a rigorous security analysis of the information leaked by Bloom filters in this case. We conduct a thorough experimental evaluation of prefiltering under a large variety of workloads. Our results indicate that prefiltering is successful at reducing the space of subscriptions to be tested in all cases. We show that while there is a tradeoff between prefiltering efficiency and information leakage when using containment obfuscation, it is practically possible to obtain good prefiltering performance while securing the technique against potential leakages.

Erasure codes have been widely used over the last decade to implement reliable data stores. They offer interesting trade-offs between efficiency, reliability, and storage overhead. Indeed, a distributed data store holding encoded data blocks can tolerate the failure of multiple nodes while requiring only a fraction of the space necessary for plain replication, albeit at an increased encoding and decoding cost. There exists nowadays a number of libraries implementing several variations of erasure codes, which notably differ in terms of complexity and implementation-specific optimizations. Seven years ago, Plank et al. [ 14 ] have conducted a comprehensive performance evaluation of open-source erasure coding libraries available at the time to compare their raw performance and measure the impact of different parameter configurations. In the present experimental study, we take a fresh perspective at the state of the art of erasure coding libraries. Not only do we cover a wider set of libraries running on modern hardware, but we also consider their efficiency when used in realistic settings for cloud-based storage, namely when deployed across several nodes in a data centre. Our measurements therefore account for the end-to-end costs of data accesses over several distributed nodes, including the encoding and decoding costs, and shed light on the performance one can expect from the various libraries when deployed in a real system. Our results reveal important differences in the efficiency of the different libraries, notably due to the type of coding algorithm and the use of hardware-specific optimizations. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We consider the allocation of coded data over nodes in a distributed storage system under a budget constraint. A system with failed nodes can recover the original data of unit size if the amount of data in the active nodes is at least a unit. Building on the work of Leong et al. [1], we introduce the concepts of tight allocations and repair bandwidth in this distributed setting. For tight allocations, the amount of data in the failed nodes gives a lower bound to the repair bandwidth required to put the system back to its original state. Using this bound, we define the Minimum Expected Repair Bandwidth (MERB) to study the tradeoffs between reliability and repair bandwidth, both empirically and by proving bounds on MERB in terms of the reliability. We show that even computing MERB for a general allocation is #P-Hard and suggest a simpler objective function to optimize it approximately. Finally, we study the asymptotic behavior of MERB for large systems and show two distinct optimal allocation regimes depending on the failure probability of the storage nodes.

Cloud-based storage services such as Dropbox, Google Drive and OneDrive are increasingly popular for storing enterprise data, and they have already become the de facto choice for cloud-based backup of hundreds of millions of regular users. Drawn by the wide range of services they provide, no upfront costs and 24/7 availability across all personal devices, customers are well-aware of the benefits that these solutions can bring. However, most users tend to forget—or worse ignore—some of the main drawbacks of such cloud-based services, namely in terms of privacy. Data entrusted to these providers can be leaked by hackers, disclosed upon request from a governmental agency's subpoena, or even accessed directly by the storage providers (e.g., for commercial benefits). While there exist solutions to prevent or alleviate these problems, they typically require direct intervention from the clients, like encrypting their data before storing it, and reduce the benefits provided such as easily sharing data between users. This practical experience report studies a wide range of security mechanisms that can be used atop standard cloud-based storage services. We present the details of our evaluation testbed and discuss the design choices that have driven its implementation. We evaluate several state-of-the-art techniques with varying security guarantees responding to user-assigned security and privacy criteria. Our results reveal the various trade-offs of the different techniques by means of representative workloads on top of industry-grade storage services.

We present STEP-archives, a model for censorship-resistant storage systems where an attacker cannot censor or tamper with data without causing a large amount of obvious collateral damage. MDS erasure codes are used to entangle unrelated data blocks, in addition to providing redundancy against storage failures. We show a tradeoff for the attacker between attack complexity, irrecoverability, and collateral damage. We also show that the system can efficiently recover from attacks with imperfect irrecoverability, making the problem asymmetric between attackers and defenders. Finally, we present sample heuristic attack algorithms that are efficient and irrecoverable (but not collateral-damage-optimal), and demonstrate how some strategies and parameter choices allow to resist these sample attacks.

The ordering of events is a fundamental problem of distributed computing and has been extensively studied over several decades. From all the available orderings, total ordering is of particular interest as it provides a powerful abstraction for building reliable distributed applications. Unfortunately, deterministic total order algorithms scale poorly and are therefore unfit for modern large-scale applications. The main contribution of this paper is EpTO, a total order algorithm with probabilistic agreement that scales both in the number of processes and events. EpTO provides deterministic safety and probabilistic liveness: integrity, total order and validity are always preserved, while agreement is achieved with arbitrarily high probability. We show that EpTO is well-suited for large-scale dynamic distributed systems: it does not require a global clock nor synchronized processes, and it is highly robust even when the network suffers from large delays and significant churn and message loss.

Content-based publish/subscribe (pub/sub) is an appealing information dissemination paradigm for distributed systems. Consumers of data subscribe to a pub/sub service, typically offered through a distributed broker overlay, and indicate their interests as constraints over the information content. Publishers generate the information flow, which the brokers filter and route to the interested subscribers. Protecting the information confidentiality, and in particular the interests of subscribers, is an important concern when brokers are located in untrusted domains such as public clouds. Encrypted matching techniques allow untrusted brokers to store encrypted subscriptions and match them against encrypted publications. Updates of encryption keys regularly happen in such contexts due to changes in trust relations. These key updates cause the invalidation of stored encrypted subscriptions and force subscribers to re-encrypt and re-submit them. This long and costly operation impacts the pub/sub service continuity and performance. In this paper, we propose a novel technique that allows updating encrypted subscriptions directly at the brokers while maintaining privacy. We present an implementation of the technique for the ASPE encrypted matching scheme and prove the security of our extension. We evaluate its practical effectiveness through a prototype implementation including a dependable key distribution protocol. Our experiments show the ability to handle key updates while preserving service continuity and performance.

Soft source decoders, in conjunction with error correcting channel codes, can be used to improve the error resilience of digital communication systems based on variable length codes. In this paper, we present a novel approach to reduce the complexity of maximum a posteriori variable length decoders implemented on a bit-symbol trellis. The decoding algorithm is implemented in a narrow corridor along the trellis diagonal to reduce the decoder complexity. Furthermore, by periodically adjusting the corridor boundaries, a significant reduction in complexity is achieved at the price of a small degradation in decoding performance.

Content-based publish/subscribe is an attractive paradigm for designing large-scale systems, as it decouples producers of information from consumers. This provides extensive flexibility for applications, which can use a modular architecture. Using this architecture, each participant expresses its interest in events by means of filters on the content of those events instead of using pre-established communication channels. However, matching events against filters has a non-negligible processing cost. Scaling the infrastructure with the number of users or events requires appropriate provisioning of resources for each of the operations involved: routing and filtering. In this paper, we propose and describe a generic, modular, and scalable infrastructure for supporting high-performance content-based publish/subscribe. We analyze its properties and show how it dynamically scales in a realistic setting. Our results provide valuable insights into the design and deployment of scalable content-based routing infrastructures.

We study the capacity of discrete memoryless channels with synchronization errors and additive noise. We first show that with very large alphabets, their capacity can be achieved by independent and identically distributed input sources, and establish proven tight lower and upper capacity bounds. We also derive tight numerical capacity bounds for channels where the synchronization between the input and output is partly preserved, for instance using incorruptible synchronization markers. Such channels include channels with duplication errors, channels that only insert or delete zeros, and channels with bitshift errors studied in magnetic recording. Channels with small alphabets and corrupted by synchronization errors have an infinite memory. Revisiting the theoretical work of Dobrushin and adapting techniques used to compute capacity bounds for finite-state source/channel models, we compute improved numerical capacity lower bounds for discrete memoryless channels with small alphabets, synchronization errors, and memoryless noise. An interesting and some- what surprising result is that as long as the input sequences are not completely deleted, the capacity of channels corrupted by discrete timing errors is always nonzero even if all the symbols are corrupted.

We study the capacity of discrete memoryless channels with synchronization errors and additive noise. We show that with very large alphabets, their capacity can be achieved by i.i.d. input sources, and prove tight lower and upper capacity bounds. An interesting result is that as long as the input sequences are not completely deleted, the capacity of channels with large alphabets corrupted by discrete timing errors is always nonzero even if all the symbols are corrupted.

In this paper, we analyze the effect of the wormhole attack on shortest-path routing protocols for wireless ad hoc networks. Using analytical and simulation results, we show that a strategic placement of the wormhole when the nodes are uniformly distributed can disrupt/control on average 32% of all communications across the network. We also analyze a scenario in which several attackers make wormholes between each other and a case where two malicious nodes attack a target node in the network. We show how to evaluate the maximum effect of the wormhole attack on a given network topology. Then, we compute the maximum effect of the wormhole attack on grid topology networks and show that the attackers can disrupt/control around 40% to 50% of all communications when the wormhole is strategically placed in the network. Finally, to defend against the wormhole attack, we propose a timing-based countermeasure that avoids the deficiencies of existing timing-based solutions. Using the proposed countermeasure, the nodes do not need synchronized clocks, nor are they required to predict the sending time or to be capable of fast switching between the receive and send modes. Moreover, the nodes do not need one-to-one communication with all their neighbors and do not require to compute a signature while having to timestamp the message with its transmission time.

We consider the problem of finding the number of subsequences when deleting symbols from a string. We present a framework to find closed-form expressions for the number of subsequences, and use it to prove the first explicit formulas for and the first formulas for nonbinary alphabets. We also present the first efficient algorithm to compute the number of subsequences for any string, number of deletions, and alphabet size.

In the interactive communication model, two parties$P_{\cal X}$and$P_{\cal Y}$possess respective private but correlated inputs$x$and$y$, and$P_{\cal Y}$wants to learn$x$from$P_{\cal X}$while minimizing the communication required for the worst possible input pair$(x,y)$. Our contribution is the analysis of four nonzero-error models in this correlated data setting. In the private coin randomized model, both players are allowed to toss coins, and$P_Y$must learn$x$with high probability for every input pair. The second and third models are similar to the first one, but the players are allowed to use a common source of randomness and to solve several independent instances of the same problem simultaneously, respectively. In the fourth model,$P_{\cal Y}$is allowed to answer incorrectly for a small fraction of the inputs. We show that one round of communication is nearly optimal for the private coin randomized model. We also prove that the last three models are equivalent and can be arbitrarily better than the original worst case deterministic model when interaction is not allowed. Finally, we show that the deterministic model and all the nonzero-error models are equivalent for a class of symmetric problems arising from several practical applications, although nonzero-error and randomization allow efficient one-way protocols.

The wormhole attack is one of the most severe security attacks in wireless ad hoc networks. In this paper, we analyze the effect of the wormhole attack in shortest path routing protocols. Using analytical and simulation results, we show that a strategic placement of the wormhole can disrupt on average 32% of all communications across the network. We also analyze a more severe attack in which several attackers make wormholes between each other and give an upper bound on the average number of communications that can be disrupted. Finally, we propose a new robust and secure on-demand distance vector routing protocol which is able to route packets as long as there is a non-faulty path between the source and the destination.

In the interactive communication model, two distant parties possess correlated inputs such as strings of bits, and the goal is for one party to learn his interlocutor's input while minimizing the communication. Our main contribution is to analyze the power of randomization in this correlated data setting. We show that the deterministic, amortized deterministic, private coin randomized, and public coin randomized models are all equivalent for a large class of problems arising from several practical applications. Furthermore, we conjecture that the private coin randomized model and the deterministic model are equivalent for every problem, and show that a proof of this statement solves the direct-sum problem for interactive communication