Proof-of-work (PoW) cryptocurrencies rely on a balance of security and fairness in order to maintain a sustainable ecosystem of miners and users. Users demand fast and consistent transaction confirmation, and in exchange drive the adoption and valuation of the cryptocurrency. Miners provide the confirmations, however, they primarily seek rewards. In unfair systems, miners can amplify their rewards by consolidating mining power. Centralization however, undermines the security guarantees of the system and might discourage users. In this paper we present Tailstorm, a cryptocurrency that strikes this balance. Tailstorm merges multiple recent protocol improvements addressing security, confirmation latency, and throughput with a novel incentive mechanism improving fairness. We implement a parallel proof-of-work consensus mechanism with $k$ PoWs per block to obtain state-of-the-art consistency guarantees. Inspired by Bobtail and Storm, we structure the individual PoWs in a tree which, by including a list of transactions with each PoW, reduces confirmation latency and improves throughput. Our proposed incentive mechanism discounts rewards based on the depth of this tree. Thereby, it effectively punishes information withholding, the core attack strategy used to reap an unfair share of rewards. We back our claims with a comprehensive analysis. We present a generic system model which allows us to specify Bitcoin, $B_k$, and Tailstorm from a joint set of assumptions. We provide an analytical bound for the fairness of Tailstorm and Bitcoin in honest networks and we confirm the results through simulation. We evaluate the effectiveness of dishonest behaviour through reinforcement learning. Our attack search reproduces known optimal strategies against Bitcoin, uncovers new ones against $B_k$, and confirms that Tailstorm's reward discounting makes it more resilient to incentive layer attacks.

The adoption of differential privacy is growing, but the complexity of designing private, efficient, and accurate algorithms is still high. We propose a novel programming framework and system, ϵ KTELO for implementing both existing and new privacy algorithms. For the task of answering linear counting queries, we show that nearly all existing algorithms can be composed from operators, each conforming to one of a small number of operator classes. While past programming frameworks have helped to ensure the privacy of programs, the novelty of our framework is its significant support for authoring accurate and efficient (as well as private) programs. After describing the design and architecture of the ϵ KTELO system, we show that ϵ KTELO is expressive, allows for safer implementations through code reuse, and allows both privacy novices and experts to easily design algorithms. We provide a number of novel implementation techniques to support the generality and scalability of ϵ KTELO operators. These include methods to automatically compute lossless reductions of the data representation, implicit matrices that avoid materialized state but still support computations, and iterative inference implementations that generalize techniques from the privacy literature. We demonstrate the utility of ϵ KTELO by designing several new state-of-the-art algorithms, most of which result from simple re-combinations of operators defined in the framework. We study the accuracy and scalability of ϵ KTELO plans in a thorough empirical evaluation.

We introduce Graphene, a method and protocol for interactive set reconciliation among peers in blockchains and related distributed systems. Through the novel combination of a Bloom filter and an Invertible Bloom Lookup Table (IBLT), Graphene uses a fraction of the network bandwidth used by deployed work for one- and two-way synchronization. We show that, for this specific problem, Graphene is more efficient at reconciling n items than using a Bloom filter at the information theoretic bound. We contribute a fast and implementation-independent algorithm for parameterizing an IBLT so that it is optimally small in size and meets a desired decode rate with arbitrarily high probability. We characterize our performance improvements through analysis, detailed simulation, and deployment results for Bitcoin Cash, a prominent cryptocurrency. Our implementations of Graphene, IBLTs, and our IBLT optimization algorithm are all open-source code.

Across many application domains, trusted parties who collect sensitive information need mechanisms to safely disseminate data. A favored approach is to generate synthetic data : a dataset similar to the original, hopefully retaining its statistical features, but one that does not reveal the private information of contributors to the data. We present PSynDB, a web-based synthetic table generator that is built on recent privacy technologies [10,11,15]. PSynDB satisfies the formal guarantee of differential privacy and generates synthetic tables with high accuracy for tasks that the user specifies as important. PSynDB allows users to browse expected error rates before running the mechanism, a useful feature for making important policy decisions, such as setting the privacy loss budget. When the user has finished configuration, the tool outputs a data synthesis program that can be ported to a trusted environment. There it can be safely executed on the private data to produce the private synthetic dataset for broad dissemination.

Ethereum contracts can be designed to function as fully decentralized applications called DAPPs that hold financial assets, and many have already been fielded. Unfortunately, DAPPs can be hacked, and the assets they control can be stolen. A recent attack on an Ethereum decentralized application called The DAO demonstrated that smart contract bugs are more than an academic concern. Ether worth hundreds of millions of US dollars was extracted by an attacker from The DAO, sending the value of its tokens and the overall exchange price of ether itself tumbling.

OneSwarm is a p2p system for anonymous file sharing. We quantify the system’s vulnerability to three attacks that identify the sources of files. First, we detail and prove that a timing attack allows a single attacker to investigate all its neighbors for possession of specific files. We prove the attack is possible due to OneSwarm’s design and is unthwarted by changes made to OneSwarm since we released our attack. Second, we show that OneSwarm is much more vulnerable to a collusion attack than previously reported, and we quantify the attack’s success given a file’s popularity, a factor not evaluated earlier. Third, we present a novel application of a known TCP-based attack. It allows a single attacker to identify whether a neighbor is the source of data or a proxy for it. Each of these attacks can be repeated as attackers quit and rejoin the network. We present these attacks in the context of forensics and the investigation of child pornography. We show that our attacks meet the higher standards required of law enforcement for criminal investigations.

The emergence of differential privacy as a primary standard for privacy protection has led to the development, by the research community, of hundreds of algorithms for various data analysis tasks. Yet deployment of these techniques has been slowed by the complexity of algorithms and an incomplete understanding of the cost to accuracy implied by the adoption of differential privacy. In this demonstration we present DPComp, a publicly-accessible web-based system, designed to support a broad community of users, including data analysts, privacy researchers, and data owners. Users can use DPComp to assess the accuracy of state-of-the-art privacy algorithms and interactively explore algorithm output in order to understand, both quantitatively and qualitatively, the error introduced by the algorithms. In addition, users can contribute new algorithms and new (non-sensitive) datasets. DPComp automatically incorporates user contributions into an evolving benchmark based on a rigorous evaluation methodology articulated by Hay et al. (SIGMOD 2016).

Client-server networks are pervasive, fundamental, and include such key networks as the Internet, power grids, and road networks. In a client-server network, clients obtain a service by connecting to one of a redundant set of servers. These networks are vulnerable to node and link failures, causing some clients to become disconnected from the servers. We develop algorithms that quantify and bound the inherent vulnerability of a clientserver network using semidefinite programming (SDP) and branch-and-cut techniques. Further, we develop a divide-and-conquer algorithm that solves the problem for large graphs. We use these techniques to show that: for the Philippine Power Grid removing just over 6% of the transmission lines will disconnect at least 20% but not more than 50% of the substations from all generators; on a large wireless mesh network disrupting 5% of wireless links between relays removes Internet access for half the relays; even after any 16% of Tier 2 ASes are removed, more than 50% of the remaining Tier 2 ASes will be connected to the Tier 1 backbone; when 300 roadblocks are erected in Michigan, it's possible to disconnect 28--43% of the population from all airports.

Disruption-Tolerant Networks (DTNs) deliver data in network environments composed of intermittently connected nodes. Just as in traditional networks, malicious nodes within a DTN may attempt to delay or destroy data in transit to its destination. Such attacks include dropping data, flooding the network with extra messages, corrupting routing tables, and counterfeiting network acknowledgments. Many existing methods for securing routing protocols require authentication supported by mechanisms such as a public key infrastructure, which is difficult to deploy and operate in a DTN, where connectivity is sporadic. Furthermore, the complexity of such mechanisms may dissuade node participation so strongly that potential attacker impacts are dwarfed by the loss of contributing participants. In this paper, we use connectivity traces from our UMass DieselNet project and the Haggle project to quantify routing attack effectiveness on a DTN that lacks security. We introduce plausible attackers and attack modalities and provide complexity results for the strongest of attackers. We show that the same routing with packet replication used to provide robustness in the face of unpredictable mobility allows the network to gracefully survive attacks. In the case of the most effective attack, acknowledgment counterfeiting, we show a straightforward defense that uses cryptographic hashes but not a central authority. We conclude that disruption-tolerant networks are extremely robust to attack; in our trace-driven evaluations, an attacker that has compromised 30% of all nodes reduces delivery rates from 70% to 55%, and to 20% with knowledge of future events. By comparison, contemporaneously connected networks are significantly more fragile.

No abstract available.