Altruism, reciprocity, and tokens to reward forwarding data: Is that fair?

V. H. Lakhani; A. Babaei; L. Jehl; G. Ishmaev; V. Estrada-Galiñanes 

Decentralized storage networks offer services with intriguing possibilities to reduce inequalities in an extremely centralized market. Fair distribution of rewards, however, is still a persistent problem in the current generation of decentralized applications using token-based incentives. They are often disproportionally concentrated with small number of early adopters and high-resourced participants. Incentive mechanisms capable of addressing this problem are still poorly understood. This paper aims to help fill this gap by developing our Tit-for-Token (Tit4Tok) model. Tit4Tok realizes incentives based on the triad of altruism (selfless behavior), reciprocity (Tit-for-Tat), and monetary rewards compatible with a free market. Tit4Tok analyzes the effects of storage-, and network-parameters fine-tuning to achieve fair distribution of rewards for participants. We present a comprehensive exploration of different factors when incentivized peers share bandwidth in a libp2p-based network, including uneven distributions emerging when gateways provide data to users outside the network. We quantified the Income-Fairness with the Gini coefficient, using multiple model instantiations and diverse approaches for debt cancellation. We propose regular changes to the gateway neighborhood and show that our shuffling method improves the Income-Fairness from 0.66 to 0.16. We quantified the non-negligible cost of tolerating free-riding (altruism). The performance is evaluated by extensive computer simulations and using an IPFS workload to study the effects of caching.

Distributed Systems – An introduction

V. Estrada-Galiñanes 

This is an introduction of the course distributed systems. I designed and created these slides to teach the DAT-520 Distributed Systems master course when I was a professor at University of Stavanger. Some slides are modified and logos were removed.

Breaking Blockchain Rationality with Out-of-Band Collusion

H. Zhang; M. Bastankhah; L-H. M. J. Merino; V. Estrada-Galinanes; B. A. Ford 

Blockchain systems often rely on rationality assumptions for their security, expecting that nodes are motivated to maximize their profits. These systems thus design their protocols to incentivize nodes to execute the honest protocol but fail to consider out-of-band collusion. Existing works analyzing rationality assumptions are limited in their scope, either by focusing on a specific protocol or relying on nonexisting financial instruments. We propose a general rational attack on rationality by leveraging an external channel that incentivizes nodes to collude against the honest protocol. Our approach involves an attacker creating an out-of-band bribery smart contract to motivate nodes to double-spend their transactions in exchange for shares in the attacker’s profits. We provide a game theory model to prove that any rational node is incentivized to follow the malicious protocol. We discuss our approach to attacking the Bitcoin and Ethereum blockchains, demonstrating that irrational behavior can be rational in real-world blockchain systems when analyzing rationality in a larger ecosystem. We conclude that rational assumptions only appear to make the system more secure and offer a false sense of security under the flawed analysis.

Towards General-Purpose Decentralized Computing with Permissionless Extensibility

Data corruption in plausible deniable storage: challenges and potential solutions

K. d’Eternod 

Workload characterization in decentralized networks

J. Simon 

QuePaxa: Escaping the Tyranny of Timeouts in Consensus

P. N. Tennage; C. Basescu; L. Kokoris-Kogias; E. Syta; P. Jovanovic et al. 

Leader-based consensus algorithms are fast and efficient under normal conditions, but lack robustness to adverse conditions due to their reliance on timeouts for liveness. We present QuePaxa, the first protocol offering state-of-the-art normal-case efficiency without depending on timeouts. QuePaxa uses a novel randomized asynchronous consensus core to tolerate adverse conditions such as denial-of-service (DoS) attacks, while a one-round-trip fast path preserves the normal-case efficiency of Multi-Paxos or Raft. By allowing simultaneous proposers without destructive interference, and using short hedging delays instead of conservative timeouts to limit redundant effort, QuePaxa permits rapid recovery after leader failure without risking costly view changes due to false timeouts. By treating leader choice and hedging delay as a multi-armed-bandit optimization, QuePaxa achieves responsiveness to prevalent conditions, and can choose the best leader even if the current one has not failed. Experiments with a prototype confirm that QuePaxa achieves normal-case LAN and WAN performance of 584k and 250k cmd/sec in throughput, respectively, comparable to Multi-Paxos. Under conditions such as DoS attacks, misconfigurations, or slow leaders that severely impact existing protocols, we find that QuePaxa remains live with median latency under 380ms in WAN experiments.

Global, Passive Detection of Connection Tampering

R. S. Raman; L-H. M. J. Merino; K. Bock; M. Fayed; D. Levin et al. 

In-network devices around the world monitor and tamper with connections for many reasons, including intrusion prevention, combating spam or phishing, and country-level censorship. Connection tampering seeks to block access to specific domain names or keywords, and it affects billions of users worldwide with little-to-no transparency. To detect, diagnose, and measure connection-level blocking, “active” measurement techniques originate queries with domains or keywords believed to be blocked and send them from vantage points within networks of interest. Active measurement efforts have been critical to understanding how traffic tampering occurs, but they inherently are unable to capture critical parts of the picture. For instance, knowing the set of domains in a block-list (i.e., what could get blocked) is not the same as knowing what real users are actively experiencing (i.e., what is actively getting blocked).|We present the first global study of connection tampering through a passive analysis of traffic received at a global CDN, Cloudflare. We analyze a sample of traffic to all of Cloudflare’s servers to construct the first comprehensive list of tampering signatures: sequences of packet headers that are indicative of connection tampering. We then apply these tampering signatures to analyze our global dataset of real user traffic, yielding a more comprehensive view of connection tampering than has been possible with active measurements alone. In particular, our passive analysis allows us to report on how connection tampering is actively affecting users and clients from virtually every network, without active probes, vantage points in difficult-to-reach networks and regions, or test lists (which we analyze for completeness against our results). Our study shows that passive measurement can be a powerful complement to active measurement in understanding connection tampering and improving transparency.

Authenticated private information retrieval

S. Colombo; K. Nikitin; H. Corrigan-Gibbs; D. J. Wu; B. A. Ford 

This paper introduces protocols for authenticated private information retrieval. These schemes enable a client to fetch a record from a remote database server such that (a) the server does not learn which record the client reads, and (b) the client either obtains the “authentic” record or detects server misbehavior and safely aborts. Both properties are crucial for many applications. Standard private-information-retrieval schemes either do not ensure this form of output authenticity, or they require multiple database replicas with an honest majority. In contrast, we offer multi-server schemes that protect security as long as at least one server is honest. Moreover, if the client can obtain a short digest of the database out of band, then our schemes require only a single server. Performing an authenticated private PGP-public-key lookup on an OpenPGP key server’s database of 3.5 million keys (3 GiB), using two non-colluding servers, takes under 1.2 core-seconds of computation, essentially matching the time taken by unauthenticated private information retrieval. Our authenticated single-server schemes are 30-100x more costly than state-of-the-art unauthenticated single-server schemes, though they achieve incomparably stronger integrity properties.

Chat2Code: A Chatbot for Model Specification and Code Generation, The Case of Smart Contracts

I. Qasse; S. Mishra; B. T. Jonsson; F. Khomh; M. Hamdaqa 

The potential of automatic code generation through Model-Driven Engineering (MDE) frameworks has yet to be realized. Beyond their ability to help software professionals write more accurate, reusable code, MDE frameworks could make programming accessible for a new class of domain experts. However, domain experts have been slow to embrace these tools, as they still need to learn how to specify their applications’ requirements using the concrete syntax (i.e., textual or graphical) of the new and unified domain-specific language. Conversational interfaces (chatbots) could smooth the learning process and offer a more interactive way for domain experts to specify their application requirements and generate the desired code. If integrated with MDE frameworks, chatbots may offer domain experts with richer domain vocabulary without sacrificing the power of agnosticism that unified modelling frameworks provide. In this paper, we discuss the challenges of integrating chatbots within MDE frameworks and then examine a specific application: the auto-generation of smart contract code based on conversational syntax. We demonstrate how this can be done and evaluate our approach by conducting a user experience survey to assess the usability and functionality of the chatbot framework. The paper concludes by drawing attention to the potential benefits of leveraging Language Models (LLMs) in this context.

Building Strongly-Consistent Systems Resilient to Failures, Partitions, and Slowdowns

Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems

C. Basescu; G. Fragkouli; E. C. Alp; M. F. Nowlan; J. M. Faleiro et al. 

Globalized computing infrastructures offer the convenience and elasticity of globally managed objects and services, but lack the resilience to distant failures that localized infrastructures such as private clouds provide. Providing both global management and resilience to distant failures, however, poses a fundamental problem for configuration services: How to discover a possibly migratory, strongly-consistent service/object in a globalized infrastructure without dependencies on globalized state? Limix is the first metadata configuration service that addresses this problem. With Limix, global strongly-consistent data-plane services and objects are insulated from remote gray failures by ensuring that the definitive, strongly-consistent metadata for any object is always confined to the same region as the object itself. Limix guarantees availability bounds: any user can continue accessing any strongly consistent object that matters to the user located at distance ∆ away, insulated from failures outside a small multiple of ∆. We built a Limix metadata service based on CockroachDB. Our experiments on Internet-like networks and on AWS, using realistic trace-driven workloads, show that Limix enables global management and significantly improves availability over the state-of-the-art.

Flash Freezing Flash Boys: Countering Blockchain Front-Running

H. Zhang; L-H. Merino; V. Estrada-Galinanes; B. Ford 

Front-running, the practice of benefiting from advanced knowledge of pending transactions, has proliferated in the cryptocurrency space with the emergence of decentralized finance. Front-running causes devastating losses to honest participants-estimated at $280M each month-and endangers the fairness of the ecosystem. We present Flash Freezing Flash Boys (F3B), an architecture to address front-running attacks by relying on a commit-and-reveal scheme where the contents of a transaction are encrypted and later revealed by a decentralized secret-management committee (SMC) when the transaction has been committed by the underlying consensus layer. To maintain legacy compatibility, we design F3B to be agnostic to the underlying consensus algorithm and compatible with existing smart contracts. A preliminary exploration of F3B shows that with a secret-management committee consisting of 8 and 128 members, F3B presents between 0.1 and 2.2 seconds of transaction-processing latency, respectively.

Efficient Deterministic Execution of Smart Contracts

E. C. Alp; C. Băsescu; P. N. Tennage; N. Kocher; G. Bosson et al. 

TRIP: Trustless Coercion-Resistant In-Person Voter Registration

L-H. Merino; S. Colombo; J. Allen; V. Estrada-Galiñanes; B. A. Ford 

Most existing remote electronic voting systems are vulnerable to voter coercion and vote buying. While coercion-resistant voting systems address this challenge, current schemes assume that the voter has access to an untappable, incorruptible device during voter registration. We present TRIP, an in-person voter registration scheme enabling voters to create verifiable and indistinguishable real and fake credentials using an untrusted kiosk inside a privacy booth at a supervised location, e.g., the registrar’s office. TRIP ensures the integrity of the voter’s real credential while enabling the creation of fake credentials using interactive zero-knowledge proofs between the voter as the verifier and the kiosk as the prover, unbeknownst to the average voter. TRIP ensures that even voters who are under extreme coercion, and cannot leave the booth with a real credential, can delegate their vote to a political party, with the caveat that they must then trust the kiosk. TRIP optimizes the tallying process by limiting the number of credentials a voter can receive and capping the number of votes that a credential can cast per election. We conduct a preliminary usability study among 41 participants at a university and found that 42.5% of participants rated TRIP a B or higher in usability, a promising result for a voter registration scheme that substantially reduces trust in the registrar.

Groove: Flexible Metadata-Private Messaging

L. Barman; M. Kol; D. Lazar; Y. Gilad; N. Zeldovich 

Metadata-private messaging designs that scale to support millions of users are rigid: they limit users to a single device that is online all the time and transmits on short regular intervals, and require users to choose precisely when each of their buddies can message them. These requirements induce high network and energy costs for the clients, restricting users to communicate via one powerful device, like their desktop.|Groove is the first scalable metadata-private messaging system that gives users flexibility: it supports users with multiple devices, allows them to message buddies at any time, even when those buddies are offline, and conserves the user’s device bandwidth and energy. Groove offers flexibility by introducing oblivious delegation, where users designate an untrusted service provider to participate in rigid mechanisms of metadata-private communication. It provides differential privacy guarantees on par with rigid systems like Stadium and Karaoke.|An evaluation of a Groove prototype on AWS with 100 servers, distributed across four data centers on two continents, demonstrates that it can achieve 32 s of latency for 1 million users with 50 buddies in their contact lists. Experiments with a client running on a Pixel 4 smartphone show that it uses about 100MB/month of bandwidth and increases battery consumption by 50mW (+16%) compared to an idle smartphone. These measurements show that Groove makes it realistic to hide messaging metadata on a mobile device.

Moby: A Blackout-Resistant Anonymity Network for Mobile Devices

A. Pradeep; H. Javaid; R. Williams; A. Rault; D. Choffnes et al. 

Internet blackouts are challenging environments for anonymity and censorship resistance. Existing popular anonymity networks (e.g., Freenet, I2P, Tor) rely on Internet connectivity to function, making them impracticable during such blackouts. In such a setting, mobile ad-hoc networks can provide connectivity, but prior communication protocols for ad-hoc networks are not designed for anonymity and attack resilience. We address this need by designing, implementing, and evaluating Moby, a blackout-resistant anonymity network for mobile devices. Moby provides end-to-end encryption, forward secrecy and sender-receiver anonymity. It features a bi-modal design of operation, using Internet connectivity when available and ad-hoc networks dur- ing blackouts. During periods of Internet connectivity, Moby functions as a regular messaging application and bootstraps information that is later used in the absence of Internet connectivity to achieve secure anonymous communications. Moby incorporates a model of trust based on users’ contact lists, and a trust establishment protocol that mitigates flooding attacks. We perform an empirically informed simulation-based study based on cellphone traces of 268,596 users over the span of a week for a large cellular provider to determine Moby’s feasibility and present our findings. Last, we implement and evaluate the Moby client as an Android app.

Auditing the Swiss Post E-voting System: An Architectural Perspective

B. A. Ford 

Switzerland is one of the few countries globally that has a national program for electronic voting (E-voting), which has been evolving in several stages for well over a decade. For the past several years, the program’s most recent stage has focused on introducing strong cryptographic verifiability into the system, together with security features such as trust splitting and a software implementation open to public inspection. Although multiple system providers have participated in the E-voting program in the past, currently the only active provider is the SwissPost. This report represents the author’s analysis of the Swiss Post’s E-voting system as part of an audit that commenced in 2021. This author’s primary role in this audit was to examine the overall architecture of the system from a high-level systems-security perspective, and to study how all the elements of the system fit together to implement an “end-to-end” electronic voting process.

Matchertext: Towards Verbatim Interlanguage Embedding

B. A. Ford 

Embedding text in one language within text of another is commonplace for numerous purposes, but usually requires tedious and error-prone “escaping” transformations on the embedded string. We propose a simple cross-language syntactic discipline, matchertext, which enables the safe embedding a string in any compliant language into a string in any other language via simple “copy-and-paste” – in particular with no escaping, obfuscation, or expansion of embedded strings. We apply this syntactic discipline to several common and frequently-embedded language syntaxes such as URIs, HTML, and JavaScript, exploring the benefits, costs, and compatibility issues in adopting the proposed matchertext discipline.

Fair Incentivization of Bandwidth Sharing in Decentralized Storage Networks

V. H. Lakhani; L. Jehl; R. Hendriksen; V. Estrada-Galinanes 

The following are the primary contributions of this study: (i) We investigate and simulate bandwidth incentives within Swarm, a cutting-edge p2p storage network; (ii) We demonstrate one approach to make the current bandwidth incentives more equitable; (iii) We use the Gini coefficient to define two quantifiable fairness characteristics to evaluate reward sharing in a decentralized p2p storage network.

Snarl: Entangled Merkle Trees for Improved File Availability and Storage Utilization

R. Nygaard; V. Estrada-Galiñanes; H. Meling 

In cryptographic decentralized storage systems, files are split into chunks and distributed across a network of peers. These storage systems encode files using Merkle trees, a hierarchical data structure that provides integrity verification and lookup services. A Merkle tree maps the chunks of a file to a single root whose hash value is the file’s content-address.A major concern is that even minor network churn can result in chunks becoming irretrievable due to the hierarchical dependencies in the Merkle tree. For example, chunks may be available but can not be found if all peers storing the root fail. Thus, to reduce the impact of churn, a decentralized replication process typically stores each chunk at multiple peers. However, we observe that this process reduces the network’s storage utilization and is vulnerable to cascading failures as some chunks are replicated 10X less than others.We propose Snarl, a novel storage component that uses a variation of alpha entanglement codes to add user-controlled redundancy to address these problems. Our contributions are summarized as follows: 1) the design of an entangled Merkle tree, a resilient data structure that reduces the impact of hierarchical dependencies, and 2) the Snarl prototype to improve file availability and storage utilization in a real-world storage network. We evaluate Snarl using various failure scenarios on a large cluster running the Ethereum Swarm network. Our evaluation shows that Snarl increases storage utilization by 5X in Swarm with improved file availability. File recovery is bandwidth-efficient and uses less than 2X chunks on average in scenarios with up to 50% of total chunk loss.

Immunizing Systems from Distant Failures by Limiting Lamport Exposure

C. Basescu; B. A. Ford 

Failures far away from a user should intuitively be less likely to affect that user. Today’s ecosystem miserably fails this test, however, despite high-availability best practices. Correlated and cascading failures – triggered by misconfigurations, bugs, and network partitions – often invalidate assumptions of failure independence. We propose that distributed services need not and should not expose local activities to distant failures or partitions, no matter how severe. Limix is an exposure-limiting architecture, guaranteeing that neither the availability nor the performance of strongly-consistent accesses within a local area may be impacted by distant failures. Preliminary results suggest that infrastructures today could use Limix to limit exposure at a manageable cost.

Technologizing Democracy or Democratizing Technology? A Layered-Architecture Perspective on Potentials and Challenges

B. A. Ford 

While technology is often claimed to be “democratizing”, the technologizing of society has more often yielded undemocratic or even anti-democratic outcomes. Is technology fundamentally at odds with democracy, or is it merely a rich and infinitely-adaptable toolbox that we’re using the wrong way? We explore how technology has failed to support robust democracy – but could do better – in the context of four basic social processes: collective deliberation and choice, information distribution and filtering, economic commerce, and identity. Technology could eventually help us make better collective choices, but only if we can make digital deliberation and voting systems both truly participatory and truly secure. Since making good decisions relies on the availability of good information, we need digital forums that enable communities to vet and filter a digital deluge of information democratically without falling into a muddle of fake news, real and perceived bias, or polarized echo chambers. Since effective participations is impractical for those who must spend every moment of time struggling to survive, healthy digital democracy will require a democratic reformulation of digital-age money and commerce as well. Finally, none of these social processes can resist abuse or subversion without a democratic basis for digital identity that can distinguish real people from abuse, botnets, and sock puppets, while preserving the privacy needed for freedom and true self-expression. While this perspective leaves many questions to answer and challenges to overcome, it does suggest a framework or layered architecture we might take as a tentative blueprint for digital democracy.

Integrity and Metadata Protection in Data Retrieval

CALYPSO: Private Data Management for Decentralized Ledgers

E. Kokoris Kogias; E. C. Alp; L. Gasser; P. S. Jovanovic; E. Syta et al. 

Distributed ledgers provide high availability and integrity, making them a key enabler for practical and secure computation of distributed workloads among mutually distrustful parties. Many practical applications also require strong confidentiality, however. This work enhances permissioned and permissionless blockchains with the ability to manage confidential data without forfeiting availability or decentralization. The proposed Calypso architecture addresses two orthogonal challenges confronting modern distributed ledgers: (a) enabling the auditable management of secrets and (b) protecting distributed computations against arbitrage attacks when their results depend on the ordering and secrecy of inputs. Calypso introduces on-chain secrets, a novel abstraction that enforces atomic deposition of an auditable trace whenever users access confidential data. Calypso provides user-controlled consent management that ensures revocation atomicity and accountable anonymity. To enable permissionless deployment, we introduce an incentive scheme and provide users with the option to select their preferred trustees. We evaluated our Calypso prototype with a confidential document-sharing application and a decentralized lottery. Our benchmarks show that transaction-processing latency increases linearly in terms of security (number of trustees) and is in the range of 0.2 to 8 seconds for 16 to 128 trustees.

Asynchronous distributed coordination and consensus with threshold logical clocks

B. Ford 

Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. The invention proposes an approach to simplify asynchronous consensus by building it atop a novel threshold logical clock abstraction, allowing the consensus protocol to operate in “virtual synchrony.” Leveraging accountable state machine techniques to detect and suppress Byzantine nodes, and verifiable secret sharing for random leader election, we obtain simple and efficient protocols for asynchronous Byzantine consensus.

Future of data sovereignty (panelist)

V. Estrada-Galiñanes 

Identity and Personhood in Digital Democracy: Evaluating Inclusion, Equality, Security, and Privacy in Pseudonym Parties and Other Proofs of Personhood

B. A. Ford 

Digital identity seems at first like a prerequisite for digital democracy: how can we ensure “one person, one vote” online without identifying voters? But the full gamut of digital identity solutions – e.g., online ID checking, biometrics, self-sovereign identity, and social/trust networks – all present severe flaws in security, privacy, and transparency, leaving users vulnerable to exclusion, identity loss or theft, and coercion. These flaws may be insurmountable because digital identity is a cart pulling the horse. We cannot achieve digital identity secure enough to support the weight of digital democracy, until we can build it on a solid foundation of digital personhood meeting key requirements. While identity is about distinguishing one person from another through attributes or affiliations, personhood is about giving all real people inalienable digital participation rights independent of identity, including protection against erosion of their democratic rights through identity loss, theft, coercion, or fakery. We explore and analyze alternative approaches to proof of personhood that might provide this missing foundation. Pseudonym parties marry the transparency of periodic physical-world roll-call events with the convenience of digital tokens between events. These tokens represent limited-term but renewable digital personhood claims, usable for purposes such as online voting or liquid democracy, sampled juries or deliberative polls, abuse-resistant social communication, or minting universal basic income in a permissionless cryptocurrency. Enhancing pseudonym parties to provide participants a moment of enforced physical security and privacy can address the coercion and vote-buying risks that plague today’s E-voting and postal voting systems alike. We also examine other recently-proposed approaches to proof of personhood, some of which offer conveniences such as all-online participation. These alternatives currently fall short of satisfying all the key digital personhood goals, unfortunately, but offer valuable insights into the challenges we face.

Design choices for Central Bank Digital Currency

S. Allen; S. Čapkun; I. Eyal; G. Fanti; B. A. Ford et al. 

Central banks around the world are exploring and in some cases even piloting central bank digital currencies (CBDCs). CBDCs promise to realize a broad range of new capabilities, including direct government disbursements to citizens, frictionless consumer payment and money-transfer systems, and a range of new financial instruments and monetary policy levers. CBDCs also give rise, however, to a host of challenging technical goals and design questions that are qualitatively and quantitatively different from those in existing government and consumer payment systems. A well-functioning CBDC will require an extremely resilient, secure, and performant new infrastructure, with the ability to onboard, authenticate, and support users on a massive scale. It will necessitate an architecture simple enough to support modular design and rigorous security analysis, but flexible enough to accommodate current and future functional requirements and use cases. A CBDC will also in some way need to address an innate tension between privacy and transparency, protecting user data from abuse while selectively permitting data mining for end-user services, policymakers, and law enforcement investigations and interventions. In this paper, we enumerate the fundamental technical design challenges facing CBDC designers, with a particular focus on performance, privacy, and security. Through a survey of relevant academic and industry research and deployed systems, we discuss the state of the art in technologies that can address the challenges involved in successful CBDC deployment. We also present a vision of the rich range of functionalities and use cases that a well-designed CBDC platform could ultimately offer users.

Que Sera Consensus: Simple Asynchronous Agreement with Private Coins and Threshold Logical Clocks

B. A. Ford; P. S. Jovanovic; E. Syta 

It is commonly held that asynchronous consensus is much more complex, difficult, and costly than partially-synchronous algorithms, especially without using common coins. This paper challenges that conventional wisdom with que sera consensus QSC, an approach to consensus that cleanly decomposes the agreement problem from that of network asynchrony. QSC uses only private coins and reaches consensus in O(1) expected communication rounds. It relies on “lock-step” synchronous broadcast, but can run atop a threshold logical clock (TLC) algorithm to time and pace partially-reliable communication atop an underlying asynchronous network. This combination is arguably simpler than partially-synchronous consensus approaches like (Multi-)Paxos or Raft with leader election, and is more robust to slow leaders or targeted network denial-of-service attacks. The simplest formulations of QSC atop TLC incur expected O(n^2) messages and O(n^4) bits per agreement, or O(n^3) bits with straightforward optimizations. An on-demand implementation, in which clients act as “natural leaders” to execute the protocol atop stateful servers that merely implement passive key-value stores, can achieve O(n^2) expected communication bits per client-driven agreement.

A Liquid Perspective on Democratic Choice

B. A. Ford 

The idea of liquid democracy responds to a widely-felt desire to make democracy more “fluid” and continuously participatory. Its central premise is to enable users to employ networked technologies to control and delegate voting power, to approximate the ideal of direct democracy in a scalable fashion that accounts for time and attention limits. There are many potential definitions, meanings, and ways to implement liquid democracy, however, and many distinct purposes to which it might be deployed. This paper develops and explores the “liquid” notion and what it might mean for purposes of enhancing voter choice by spreading voting power, improving proportional representation systems, simplifying or aiding voters in their choice, or scaling direct democracy through specialization. The goal of this paper is to disentangle and further develop some of the many concepts and goals that liquid democracy ideas often embody, to explore their justification with respect to existing democratic traditions such as transferable voting and political parties, and to explore potential risks in liquid democracy systems and ways to address them.

Democratic Value and Money for Decentralized Digital Society

B. A. Ford 

Classical monetary systems regularly subject the most vulnerable majority of the world’s population to debilitating financial shocks, and have manifestly allowed uncontrolled global inequality over the long term. Given these basic failures, how can we avoid asking whether mainstream macroeconomic principles are actually compatible with democratic principles such as equality or the protection of human rights and dignity? This idea paper takes a constructive look at this question, by exploring how alternate monetary principles might result in a form of money more compatible with democratic principles — dare we call it “democratic money”? In this alternative macroeconomic philosophy, both the supply of and the demand for money must be rooted in people, so as to give all people both equal opportunities for economic participation. Money must be designed around equality, not only across all people alive at a given moment, but also across past and future generations of people, guaranteeing that our descendants cannot be enslaved by their ancestors’ economic luck or misfortune. Democratic money must reliably give all people a means to enable everyday commerce, investment, and value creation in good times and bad, and must impose hard limits on financial inequality. Democratic money must itself be governed democratically, and must economically facilitate the needs of citizens in a democracy for trustworthy and unbiased information with which to make wise collective decisions. An intriguing approach to implementing and deploying democratic money is via a cryptocurrency built on a proof-of-personhood foundation, giving each opt-in human participant one equal unit of stake. Such a cryptocurrency would have both interesting similarities to, and important differences from, a Universal Basic Income (UBI) denominated in an existing currency.

PriFi: Low-Latency Anonymity for Organizational Networks

L. Barman; I. Dacosta; M. Zamani; E. Zhai; A. Pyrgelis et al. 

Organizational networks are vulnerable to traffic-analysis attacks that enable adversaries to infer sensitive information from the network traffic – even if encryption is used. Typical anonymous communication networks are tailored to the Internet and are poorly suited for organizational networks. We present PriFi, an anonymous communication protocol for LANs: it protects users against eavesdroppers and provides traffic-analysis resistance. PriFi builds on Dining Cryptographers networks but reduces the high communication latency of prior work via a new client/relay/server architecture, in which a client’s packets remain on their usual network path without additional hops, and in which a set of remote servers assist the anonymization process without adding latency. PriFi also solves the challenge of equivocation attacks, which are not addressed by related works, by encrypting the traffic based on the communication history. Our evaluation shows that PriFi introduces a small latency overhead (≈ 100ms for 100 clients) and is compatible with delay-sensitive applications such as Voice-over-IP.

SafetyPin: Encrypted Backups with Human-Memorable Secrets

E. Dauterman; H. Corrigan-Gibbs; D. Mazieres 

We present the design and implementation of SafetyPin, a system for encrypted mobile-device backups. Like existing cloud-based mobile-backup systems, including those of Apple and Google, SafetyPin requires users to remember only a short PIN and defends against brute-force PIN-guessing attacks using hardware security protections. Unlike today’s systems, SafetyPin splits trust over a cluster of hardware security modules (HSMs) in order to provide security guarantees that scale with the number of HSMs. In this way, SafetyPin protects backed-up user data even against an attacker that can adaptively compromise many of the system’s constituent HSMs. SafetyPin provides this protection without sacrificing scalability or fault tolerance. Decentralizing trust while respecting the resource limits of today’s HSMs requires a synthesis of systems-design principles and cryptographic tools. We evaluate SafetyPin on a cluster of 100 low-cost HSMs and show that a SafetyPin-protected recovery takes 1.01 seconds. To process 1B recoveries a year, we estimate that a SafetyPin deployment would need 3,100 low-cost HSMs.

Replicated state machines without replicated execution

J. Lee; K. Nikitin; S. Setty 

This paper introduces a new approach to reduce end-to-end costs in large-scale replicated systems built under a Byzantine fault model. Specifically, our approach transforms a given replicated state machine (RSM) to another RSM where nodes incur lower costs by delegating state machine execution: an untrusted prover produces succinct cryptographic proofs of correct state transitions along with state changes, which nodes in the transformed RSM verify and apply respectively. To realize our approach, we build Piperine, a system that makes the proof machinery profitable in the context of RSMs. Specifically, Piperine reduces the costs of both proving and verifying the correctness of state machine execution while retaining liveness-a distinctive requirement in the context of RSMs. Our experimental evaluation demonstrates that, for a payment service, employing Piperine is more profitable than naive reexecution of transactions as long as there are more than 10^4 nodes. When we apply Piperine to ERC-20 transactions in Ethereum (a real-world RSM with up to 10^5 nodes), it reduces per-transaction costs by 5.4× and network costs by 2.7×.

SafetyPin: Encrypted Backups with Human-Memorable Secrets

E. Dauterman; H. Corrigan-Gibbs; D. Mazières 

We present the design and implementation of SafetyPin, a system for encrypted mobile-device backups. Like existing cloud-based mobile-backup systems, including those of Apple and Google, SafetyPin requires users to remember only a short PIN and defends against brute-force PIN-guessing attacks using hardware security protections. Unlike today’s systems, SafetyPin splits trust over a cluster of hardware security modules (HSMs) in order to provide security guarantees that scale with the number of HSMs. In this way, SafetyPin protects backed-up user data even against an attacker that can adaptively compromise many of the system’s constituent HSMs. SafetyPin provides this protection without sacrificing scalability or fault tolerance. Decentralizing trust while respecting the resource limits of today’s HSMs requires a synthesis of systems-design principles and cryptographic tools. We evaluate SafetyPin on a cluster of 100 low-cost HSMs and show that a SafetyPin-protected recovery takes 1.01 seconds. To process 1B recoveries a year, we estimate that a SafetyPin deployment would need 3,100 low-cost HSMs.

Drynx: Decentralized, Secure, Verifiable System for Statistical Queries and Machine Learning on Distributed Datasets

D. Froelicher; J. R. Troncoso-Pastoriza; J. S. Sousa; J-P. Hubaux 

Data sharing has become of primary importance in many domains such as big-data analytics, economics and medical research, but remains difficult to achieve when the data are sensitive. In fact, sharing personal information requires individuals’ unconditional consent or is often simply forbidden for privacy and security reasons. In this paper, we propose Drynx, a decentralized system for privacy-conscious statistical analysis on distributed datasets. Drynx relies on a set of computing nodes to enable the computation of statistics such as standard deviation or extrema, and the training and evaluation of machine-learning models on sensitive and distributed data. To ensure data confidentiality and the privacy of the data providers, Drynx combines interactive protocols, homomorphic encryption, zero-knowledge proofs of correctness, and differential privacy. It enables an efficient and decentralized verification of the input data and of all the system’s computations thus provides auditability in a strong adversarial model in which no entity has to be individually trusted. Drynx is highly modular, dynamic and parallelizable. Our evaluation shows that it enables the training of a logistic regression model on a dataset (12 features and 600,000 records) distributed among 12 data providers in less than 2 seconds. The computations are distributed among 6 computing nodes, and Drynx enables the verification of the query execution’s correctness in less than 22 seconds.

[Invited Talk] Building a Disaster-resilient Storage Layer for Next Generation Networks: The Role of Redundancy

V. Estrada-Galiñanes; R. Nygaard; V. Tron; R. Saramago; L. Jehl et al. 

MorphIT: Morphing Packet Reports for Internet Transparency

G. Fragkouli; K. Argyraki; B. A. Ford 

Can we improve Internet transparency without worsening user anonymity? For a long time, researchers have been proposing transparency systems, where traffic reports produced at strategic network points help assess network behavior and verify service-level agreements or neutrality compliance. However, such reports necessarily reveal when certain traffic appeared at a certain network point, and this information could, in principle, be used to compromise low-latency anonymity networks like Tor. In this paper, we examine whether more Internet transparency necessarily means less anonymity. We start from the information that a basic transparency solution would publish about a network and study how that would impact the anonymity of the network’s users. Then we study how to change, in real time, the time granularity of traffic reports in order to preserve both user anonymity and report utility. We evaluate with real and synthetic data and show that our algorithm can offer a good anonymity/utility balance, even in adversarial scenarios where aggregates consist of very few flows.

Open Humans: A platform for participant-centered research and personal data exploration

B. Greshake Tzovaras; M. Angrist; K. Arvai; M. Dulaney; V. Estrada-Galiñanes et al. 

Threshold Logical Clocks for Asynchronous Distributed Coordination and Consensus

B. A. Ford 

Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. This paper attempts to simplify asynchronous consensus by building atop a novel threshold logical clock abstraction, which enables upper layers to operate as if on a synchronous network. This approach yields an asynchronous consensus protocol for fail-stop nodes that may be simpler and more robust than Paxos and its leader-based variants, requiring no common coins and achieving consensus in a constant expected number of rounds. The same approach can be strengthened against Byzantine failures by building on well-established techniques such as tamper-evident logging and gossip, accountable state machines, threshold signatures and witness cosigning, and verifiable secret sharing. This combination of existing abstractions and threshold logical clocks yields a modular, cleanly-layered approach to building practical and efficient Byzantine consensus, distributed key generation, time, timestamping, and randomness beacons, and other critical services.

MedChain: Accountable and Auditable Data Sharing in Distributed Medical Scenarios

J. R. Troncoso-Pastoriza; J. L. Raisaro; L. Gasser; B. A. Ford; J-P. Hubaux 

The current trend towards personalized medicine creates an urgent need to share data among different hospitals and health institutions, which endangers the privacy of the data subjects if not done with the appropriate precautions. Conversely, the frequency of data breaches in the healthcare industry has been rising since 2010, severely holding back health institutions from exposing and sharing their data for the fear of being the next target of cyberattacks. In this landscape, the ability to provide strong auditability, accountability and traceability of the system events plays a role as important as data confidentiality for the purpose of enabling secure and privacy-conscious data sharing, breach detection and fast recovery. National and international regulations (e.g., HIPAA in the United States and the GDPR in Europe) impose strong requirements both in terms of confidentiality, i.e., prevention of undue data leakages and restriction of data access, and accountability, i.e., recording of all data accesses and exchanges carried out by any entity with the purpose of identifying misbehaving individuals. This is especially relevant for medical and genomic data, whose (un)intended leakage can severely harm individuals’ privacy and institutions’ reputation. Current operational systems for medical data sharing are lacking in terms of privacy protection and/or transparency guarantees that can address these challenges, and they provide a weak federated or centralized model of identity and access control that can endanger the whole network if only one of the sites is breached. In this talk, we propose MedChain, a novel system featuring distributed, flexible and fully decentralized identity management and access control mechanisms based on distributed ledger technologies, that enable (a) full traceability, auditability and accountability of all system events through immutable logs with no single point of failure, particularly dealing with the access to and usage of medical and genomic data, and (b) fine-grained configurable and privacy-conscious access control enforced through smart contracts (protocols to digitally enforce and verify the execution of a set of agreed actions). We exemplify the use of the system through an application to distributed feasibility studies, by integrating it in the currently most widespread cohort explorer tools (i2b2 and SHRINE).

On the Security of Two-Round Multi-Signatures

M. Drijvers; K. Edalatnejad; B. Ford; E. Kiltz; J. Loss et al. 

A multi-signature scheme allows a group of signers to collaboratively sign a message, creating a single signature that convinces a verifier that every individual signer approved the message. The increased interest in technologies to decentralize trust has triggered the proposal of highly efficient two-round Schnorr-based multi-signature schemes designed to scale up to thousands of signers, namely BCJ by Bagherzandi et al. (CCS 2008), MWLD by Ma et al. (DCC 2010), CoSi by Syta et al. (S&P 2016), and MuSig by Maxwell et al. (ePrint 2018). In this work, we point out serious security issues in all currently known two-round multi-signature schemes (without pairings). First, we prove that none of the schemes can be proved secure without radically departing from currently known techniques. Namely, we show that if the one-more discrete-logarithm problem is hard, then no algebraic reduction exists that proves any of these schemes secure under the discrete-logarithm or one-more discrete-logarithm problem. We point out subtle flaws in the published security proofs of the above schemes (except CoSi, which was not proved secure) to clarify the contradiction between our result and the existing proofs. Next, we describe practical sub exponential attacks on all schemes, providing further evidence to their insecurity. Being left without two-round multi-signature schemes, we present rnBCJ, a variant of the BCJ scheme that we prove secure under the discrete-logarithm assumption in the random-oracle model. Our experiments show that rni3CJ barely affects scalability compared to CoSi, allowing 16384 signers to collaboratively sign a message in about 2 seconds, making it a highly practical and provably secure alternative for large-scale deploy tents.

Methods and systems for secure data exchange

B. Ford; L. Gasser; E. Kokoris Kogias; P. Janovic 

The present invention concerns a computer-implemented method for secure data exchange between a sender (A) and a recipient (B), wherein the method is performed by the sender (A) and comprises encrypting data using a symmetric key k, creating a write transaction T W , wherein the write transaction T W comprises information usable to derive the symmetric key k and an access policy identifying the recipient (B) as being allowed to decrypt the encrypted data, providing the recipient (B) access to the encrypted data, and sending the write transaction T W to a first group of servers (AC) for being stored in a blockchain data structure maintained by the first group of servers (AC).

Reducing Metadata Leakage from Encrypted Files and Communication with PURBs

K. Nikitin; L. Barman; W. Lueks; M. J. Underwood; J-P. Hubaux et al. 

Most encrypted data formats leak metadata via their plaintext headers, such as format version, encryption schemes used, number of recipients who can decrypt the data, and even the recipients’ identities. This leakage can pose security and privacy risks to users, e.g., by revealing the full membership of a group of collaborators from a single encrypted e-mail, or by enabling an eavesdropper to fingerprint the precise encryption software version and configuration the sender used. We propose that future encrypted data formats improve security and privacy hygiene by producing Padded Uniform Random Blobs or PURBs: ciphertexts indistinguishable from random bit strings to anyone without a decryption key. A PURB’s content leaks nothing at all, even the application that created it, and is padded such that even its length leaks as little as possible. Encoding and decoding ciphertexts with no cleartext markers presents efficiency challenges, however. We present cryptographically agile encodings enabling legitimate recipients to decrypt a PURB efficiently, even when encrypted for any number of recipients’ public keys and/or passwords, and when these public keys are from different cryptographic suites. PURBs employ Padmé, a novel padding scheme that limits information leakage via ciphertexts of maximum length M to a practical optimum of O(log log M) bits, comparable to padding to a power of two, but with lower overhead of at most 12% and decreasing with larger payloads.

Beyond Conventional Security in Sponge-Based Authenticated Encryption Modes

P. Jovanovic; A. Luykx; B. Mennink; Y. Sasaki; K. Yasuda 

The Sponge function is known to achieve 2c/2 security, where c is its capacity. This bound was carried over to its keyed variants, such as SpongeWrap, to achieve a min{2c/2,2 kappa} security bound, with kappa the key length. Similarly, many CAESAR competition submissions were designed to comply with the classical 2c/2 security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of min{2b/2,2c,2 kappa}, with b>c the permutation size, by proving that the CAESAR submission NORX achieves this bound. The proof relies on rigorous computation of multi-collision probabilities, which may be of independent interest. We additionally derive a generic attack based on multi-collisions that matches the bound. We show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of some of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. We finally consider the remaining one of the three PRIMATEs, APE, and derive a blockwise adaptive attack in the nonce-respecting setting with complexity 2c/2, therewith demonstrating that the techniques cannot be applied to APE.

Rethinking General-Purpose Decentralized Computing

E. C. Alp; E. Kokoris-Kogias; G. Fragkouli; B. Ford 

While showing great promise, smart contracts are difficult to program correctly, as they need a deep understanding of cryptography and distributed algorithms, and offer limited functionality, as they have to be deterministic and cannot operate on secret data. In this paper we present Protean, a general-purpose decentralized computing platform that addresses these limitations by moving from a monolithic execution model, where all participating nodes store all the state and execute every computation, to a modular execution-model. Protean employs secure specialized modules, called functional units, for building decentralized applications that are currently insecure or impossible to implement with smart contracts. Each functional unit is a distributed system that provides a special-purpose functionality by exposing atomic transactions to the smart-contract developer. Combining these transactions into arbitrarily-defined workflows, developers can build a larger class of decentralized applications, such as provably-secure and fair lotteries or e-voting.

MedCo: Enabling Secure and Privacy-Preserving Exploration of Distributed Clinical and Genomic Data

J. L. Raisaro; J. R. Troncoso-Pastoriza; M. Misbach; J. A. Gomes de Sá E Sousa; S. Pradervand et al. 

The increasing number of health-data breaches is creating a complicated environment for medical-data sharing and, consequently, for medical progress. Therefore, the development of new solutions that can reassure clinical sites by enabling privacy-preserving sharing of sensitive medical data in compliance with stringent regulations (e.g., HIPAA, GDPR) is now more urgent than ever. In this work, we introduce MedCo, the first operational system that enables a group of clinical sites to federate and collectively protect their data in order to share them with external investigators without worrying about security and privacy concerns. MedCo uses (a) collective homomorphic encryption to provide trust decentralization and end-to-end confidentiality protection, and (b) obfuscation techniques to achieve formal notions of privacy, such as differential privacy. A critical feature of MedCo is that it is fully integrated within the i2b2 (Informatics for Integrating Biology and the Bedside) framework, currently used in more than 300 hospitals worldwide. Therefore, it is easily adoptable by clinical sites. We demonstrate MedCo’s practicality by testing it on data from The Cancer Genome Atlas in a simulated network of three institutions. Its performance is comparable to the ones of SHRINE (networked i2b2), which, in contrast, does not provide any data protection guarantee.

Alpha Entanglement Codes: Practical Erasure Codes to Archive Data in Unreliable Environments

V. Estrada-Galiñanes; E. Miller; P. Felber; J-F. Paris 

System and method for providing a collective decentralized authority for sharing sensitive data

B. Ford; J-P. Hubaux; P. Egger; J-L. Raisaro; Z. Huang 

A method of sharing private and/or sensitive data from plurality of data providers to a data user, the data user having a private key and a public key, the method comprising the steps of providing a first data set and encrypting the first data set at a terminal of a first data provider with a collective public key, providing a second data set and encrypting the second data set at a terminal of a second data provider with the collective public key, sending the encrypted data to a server from the plurality of servers, the plurality of servers forming together a collective and decentralized authority, decentralized aggregating the encrypted data of the first and second data providers by the plurality of servers, based on the homomorphic encryption scheme, to compute a first encrypted aggregated data set, modifying the encryption of the first encrypted aggregated data set from the encryption based on the collective public key to an encryption based on the public key of the data user to generate a second encrypted aggregated data set.

Systems and method for anonymous, low-latencey, tracking-resistant communications in a networked environment

B. Ford; L. Barman; J-P. Hubaux; I. Dacosta; J. Feigenbaum 

Exemplary embodiments of the present disclosure provide cryptographically-strong tracking protection with unnoticeable “single-hop” network latencies by leveraging a client-relay- server architecture, in which the clients, relays (trusted or untrusted), and trustee devices are configured to implement a distributed anonymity protocol where the anonymization function adds little to no latency to the network.

Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods

B. Ford; L. Gasser; E. K. Kogias; P. Jovanovic 

Data storage and retrieval systems, methods, and computer-readable media utilize a cryptographically verifiable data structure that facilitates verification of a transaction in a decentralized peer-to-peer environment using multi-hop backwards and forwards links. Backward links are cryptographic hashes of past records. Forward links are cryptographic signatures of future records that are added retroactively to records once the target block has been appended to the data structure.

A Blockchain Consensus Protocol With Horizontal Scalability

K. Cong; Z. Ren; J. Pouwelse 

Blockchain technology has the potential to decentralise many traditionally centralised systems. However, scalability remains a key challenge. A horizontally scalable solution, where performance increases by adding more nodes, would move blockchain systems one step closer to ubiquitous use. We design a novel blockchain system called CHECO. Each node in our system maintains a personal hash chain, which only stores transactions that the node is involved in. A consensus is reached on special blocks called checkpoint blocks rather than on all transactions. Checkpoint blocks are effectively a hash pointer to the personal hash chains; thus a single checkpoint block may represent an arbitrarily large set of transactions. We introduce a validation protocol so that any node can check the validity of any transaction. Since transaction and validation protocols are point-to-point, we achieve horizontal scalability. We analytically evaluate our system and show a number of highly desirable correctness properties such as consensus on the validity of transactions. Further, we give a free and open-source implementation of CHECO and evaluate it experimentally. Our results show a strong indication of horizontal scalability.

Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter!

A. Boutet; F. De Moor; D. Frey; R. Guerraoui; A-M. Kermarrec et al. 

Recommendation systems help users identify interesting content, but they also open new privacy threats. In this paper, we deeply analyze the effect of a Sybil attack that tries to infer information on users from a user-based collaborative-filtering recommendation systems. We discuss the impact of different similarity metrics used to identity users with similar tastes in the trade-off between recommendation quality and privacy. Finally, we propose and evaluate a novel similarity metric that combines the best of both worlds: a high recommendation quality with a low prediction accuracy for the attacker. Our results, on a state-of-the-art recommendation framework and on real datasets show that existing similarity metrics exhibit a wide range of behaviors in the presence of Sybil attacks, while our new similarity metric consistently achieves the best trade-off while outperforming state-of-the-art solutions.

A Scale-out Blockchain for Value Transfer with Spontaneous Sharding

Z. Ren; K. Cong; T. V. Aerts; B. A. P. de Jonge; A. F. Morais et al. 

In this paper, we show that the complete set of transactions is not a necessity for the prevention of double-spending if the properties of value transfers is fully explored. In other words, we show that a value-transfer ledger like Bitcoin has the potential to scale-out by its nature without sacrificing security or decentralization. Firstly, we give a formal definition for the value-transfer ledger and its distinct features from a generic database. Then, we introduce the blockchain structure with a shared main chain for consensus and an individual chain for each node for recording transactions. A locally executable validation scheme is proposed with uncompromising validity and consistency. A beneficial consequence of our design is that nodes will spontaneously try to reduce their transmission cost by only providing the transactions needed to show that their transactions are not double spend. As a result, the network is sharded as each node only acquires part of the transaction record and a scale-out throughput could be achieved, which we call “spontaneous sharding”.

Channels: Horizontal Scaling and Confidentiality on Permissioned Blockchains

E. Androulaki; C. Cachin; A. De Caro; E. Kokoris-Kogias 

Sharding, or partitioning the system’s state so that different subsets of participants handle it, is a proven approach to building distributed systems whose total capacity scales horizontally with the number of participants. Many distributed ledgers have adopted this approach to increase their performance, however, they focus on the permissionless setting that assumes the existence of a strong adversary. In this paper, we deploy channels for permissioned blockchains. Our first contribution is to adapt sharding on asset-management applications for the permissioned setting, while preserving liveness and safety even on transactions spanning across-channels. Our second contribution is to leverage channels as a confidentiality boundary, enabling different organizations and consortia to preserve their privacy within their channels and still be part of a bigger collaborative ecosystem. To make our system concrete we map it on top of Hyperledger Fabric.

Channels: Horizontal Scaling and Confidentiality on Permissioned Blockchains with Application on Hyperledger Fabric

E. Androulaki; C. Cachin; A. De Caro; E. Kokoris Kogias 

Sharding, or partitioning the system’s state so that different subsets of participants handle it, is a proven approach to building distributed systems whose total capacity scales horizontally with the number of participants. Many distributed ledgers have adopted this approach to increase their performance, however, they focus on the permissionless setting that assumes the existence of a strong adversary. In this paper, we deploy channels for permissioned blockchains. Our first contribution is to adapt sharding on asset-management applications for the permissioned setting, while preserving liveness and safety even on transactions spanning across-channels. Our second contribution is to leverage channels as a confidentiality boundary, enabling different organizations and consortia to preserve their privacy within their channels and still be part of a bigger collaborative ecosystem. To make our system concrete we map it on top of Hyperledger Fabric.

On Enforcing the Digital Immunity of a Large Humanitarian Organization

S. Le Blond; A. Cuevas; J. R. Troncoso-Pastoriza; P. S. Jovanovic; B. A. Ford et al. 

Humanitarian action, the process of aiding individuals in situations of crises, poses unique information-security challenges due to natural or manmade disasters, the adverse environments in which it takes place, and the scale and multidisciplinary nature of the problems. Despite these challenges, humanitarian organizations are transitioning towards a strong reliance on the digitization of collected data and digital tools, which improves their effectiveness but also exposes them to computer-security threats. In this paper, we conduct a qualitative analysis of the computer-security challenges of the International Committee of the Red Cross (ICRC), a large humanitarian organization with over sixteen thousand employees, an international legal personality, which involves privileges and immunities, and over 150 years of experience with armed conflicts and other situations of violence worldwide. To investigate the computer security needs and practices of the ICRC from an operational, technical, legal, and managerial standpoint by considering individual, organizational, and governmental levels, we interviewed 27 field workers, IT staff, lawyers, and managers. Our results provide a first look at the unique security and privacy challenges that humanitarian organizations face when collecting, processing, transferring, and sharing data to enable humanitarian action for a multitude of sensitive activities. These results highlight, among other challenges, the trade-offs between operational security and requirements stemming from all stakeholders, the legal barriers for data sharing among jurisdictions; especially, the need to complement privileges and immunities with robust technological safeguards in order to avoid any leakages that might hinder access and potentially compromise the neutrality, impartiality, and independence of humanitarian action.

OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding

E. Kokoris Kogias; P. S. Jovanovic; L. Gasser; N. Gailly; E. Syta et al. 

Designing a secure permissionless distributed ledger (blockchain) that performs on par with centralized payment processors, such as Visa, is a challenging task. Most existing distributed ledgers are unable to scale-out, i.e., to grow their total processing capacity with the number of validators; and those that do, compromise security or decentralization. We present OmniLedger, a novel scale-out distributed ledger that preserves longterm security under permissionless operation. It ensures security and correctness by using a bias-resistant public-randomness protocol for choosing large, statistically representative shards that process transactions, and by introducing an efficient crossshard commit protocol that atomically handles transactions affecting multiple shards. OmniLedger also optimizes performance via parallel intra-shard transaction processing, ledger pruning via collectively-signed state blocks, and low-latency “trust-butverify” validation for low-value transactions. An evaluation of our experimental prototype shows that OmniLedger’s throughput scales linearly in the number of active validators, supporting Visa-level workloads and beyond, while confirming typical transactions in under two seconds.

Practical erasure codes for storage systems: The study of entanglement codes, an approach that propagates redundancy to increase reliability and performance

Atom: Horizontally Scaling Strong Anonymity

A. Kwon; H. Corrigan-Gibbs; S. Devadas; B. A. Ford 

Atom is an anonymous messaging system that protects against traffic-analysis attacks. Unlike many prior systems, each Atom server touches only a small fraction of the total messages routed through the network. As a result, the system’s capacity scales near-linearly with the number of servers. At the same time, each Atom user benefits from “best possible” anonymity: a user is anonymous among all honest users of the system, even against an active adversary who monitors the entire network, a portion of the system’s servers, and any number of malicious users. The architectural ideas behind Atom have been known in theory, but putting them into practice requires new techniques for (1) avoiding heavy general-purpose multi-party computation protocols, (2) defeating active attacks by malicious servers at minimal performance cost, and (3) handling server failure and churn. Atom is most suitable for sending a large number of short messages, as in a microblogging application or a high-security communication bootstrapping (“dialing”) for private messaging systems. We show that, on a heterogeneous network of 1,024 servers, Atom can transit a million Tweet-length messages in 28 minutes. This is over 23× faster than prior systems with similar privacy guarantees.

Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies

M. F. Borge Chavez; E. Kokoris Kogias; P. S. Jovanovic; L. Gasser; N. Gailly et al. 

Permissionless blockchain-based cryptocurrencies commonly use proof-of-work (PoW) or proof-of-stake (PoS) to ensure their security, e.g. to prevent double spending attacks. However, both approaches have disadvantages: PoW leads to massive amounts of wasted electricity and re-centralization, whereas major stakeholders in PoS might be able to create a monopoly. In this work, we propose proof-of-personhood (PoP), a mechanism that binds physical entities to virtual identities in a way that enables accountability while preserving anonymity. Afterwards we introduce PoPCoin, a new cryptocurrency, whose consensus mechanism leverages PoP to eliminate the disadvantages of PoW and PoS while ensuring security. PoPCoin leads to a continuously fair and democratic wealth creation process which paves the way for an experimental basic income infrastructure.

Multiple Objectives of Lawful-Surveillance Protocols

J. Feigenbaum; B. A. Ford 

In recent work on open, privacy-preserving, accountable surveillance, we have proposed the use of cryptographic protocols that enable law-enforcement and intelligence agencies to obtain actionable information about targeted users of mass-communication systems without intruding on the privacy of untargeted users. Our suggestion that appropriate technology, combined with sound policy and the rule of law, can afford typical users significantly more privacy than they have now without hindering lawful and effective actions by law-enforcement and intelligence agencies has met with considerable skepticism. In this paper, we summarize the principal objections to our approach and address them.

MedCo: Enabling Privacy-Conscious Exploration of Distributed Clinical and Genomic Data

J. L. Raisaro; J. R. Troncoso-Pastoriza; M. Misbach; J. A. Gomes de Sá E Sousa; S. Pradervand et al. 

Being able to share large amounts of sensitive clinical and genomic data across several institutions is crucial for precision medicine to scale up. Unfor- tunately, existing solutions only partially address this challenge and are still unable to provide the strong privacy and security guarantees required by regulations (e.g., HIPAA, GDPR). As a result, currently only very limited datasets of non-sensitive and moderately useful information can be shared. In this paper, we introduce MedCo, the first operational system that enables an investigator to explore sensi- tive medical information distributed at several sites and protected with collective homomorphic encryption. MedCo builds on top of established and widespread technology from the biomedical informatics community, such as i2b2 and SHRINE, and relies on state-of-the-art secure protocols for processing encrypted distributed data and complying with regulations. As such, MedCo can be easily adopted by clinical sites thus paving the way to new unexplored data-sharing use cases. We tested MedCo in a real network of three institutions (EPFL, UNIL and CHUV) by focusing on an oncology use-case with real somatic mutations and clinical tumor data. The relatively low overhead introduced by MedCo shows that it represents a concrete and scalable solution for sharing privacy-conscious medical data.

Scalable Bias-Resistant Distributed Randomness

E. Syta; P. S. Jovanovic; E. Kokoris Kogias; N. Gailly; L. Gasser et al. 

Bias-resistant public randomness is a critical component in many (distributed) protocols. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.

CHAINIAC: Proactive Software-Update Transparency via Collectively Signed Skipchains and Verified Builds

K. Nikitin; E. Kokoris Kogias; P. S. Jovanovic; L. Gasser; N. Gailly et al. 

Software-update mechanisms are critical to the security of modern systems, but their typically centralized design presents a lucrative and frequently attacked target. In this work, we propose CHAINIAC, a decentralized software-update framework that eliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent witness servers collectively verify conformance of software updates to release policies, build verifiers validate the source-to-binary correspondence, and a tamper-proof release log stores collectively signed updates, thus ensuring that no release is accepted by clients before being widely disclosed and validated. The release log embodies a skipchain, a novel data structure, enabling arbitrarily out-of-date clients to efficiently validate updates and signing keys. Evaluation of our CHAINIAC prototype on reproducible Debian packages shows that the automated update process takes the average of 5 minutes per release for individual packages, and only 20 seconds for the aggregate timeline. We further evaluate the framework using real-world data from the PyPI package repository and show that it offers clients security comparable to verifying every single update themselves while consuming only one-fifth of the bandwidth and having a minimal computational overhead.

Axiom: DTLS-Based Secure IoT Group Communication

M. Tiloca; K. Nikitin; S. Raza 

This article presents Axiom, a DTLS-based approach to efficiently secure multicast group communication among IoT-constrained devices. Axiom provides an adaptation of the DTLS record layer, relies on key material commonly shared among the group members, and does not require one to perform any DTLS handshake. We made a proof-of-concept implementation of Axiom based on the tinyDTLS library for the Contiki OS and used it to experimentally evaluate performance of our approach on real IoT hardware. Results show that Axiom is affordable on resource-constrained platforms and performs significantly better than related alternative approaches.

UnLynx: A Decentralized System for Privacy-Conscious Data Sharing

D. Froelicher; P. Egger; J. S. Sousa; J. L. Raisaro; Z. Huang et al. 

Current solutions for privacy-preserving data sharing among multiple parties either depend on a centralized authority that must be trusted and provides only weakest-link security (e.g., the entity that manages private/secret cryptographic keys), or leverage on decentralized but impractical approaches (e.g., secure multi-party computation). When the data to be shared are of a sensitive nature and the number of data providers is high, these solutions are not appropriate. Therefore, we present UnLynx, a new decentralized system for efficient privacypreserving data sharing. We consider m servers that constitute a collective authority whose goal is to verifiably compute on data sent from n data providers. UnLynx guarantees the confidentiality, unlinkability between data providers and their data, privacy of the end result and the correctness of computations by the servers. Furthermore, to support differentially private queries, UnLynx can collectively add noise under encryption. All of this is achieved through a combination of a set of new distributed and secure protocols that are based on homomorphic cryptography, verifiable shuffling and zero-knowledge proofs. UnLynx is highly parallelizable and modular by design as it enables multiple security/privacy vs. runtime tradeoffs. Our evaluation shows that UnLynx can execute a secure survey on 400,000 personal data records containing 5 encrypted attributes, distributed over 20 independent databases, for a total of 2,000,000 ciphertexts, in 24 minutes.

Low-latency Blockchain Consensus

C. Basescu; E. Kokoris-Kogias; B. A. Ford 

Blockchains are increasingly attractive due to their decentralization, yet inherent limitations of high latency, in the order of minutes, and attacks on consensus cap their practicality. We introduce Blinkchain, a Byzantine consensus protocol that relies on sharding and locality-preserving techniques from distributed systems to provide a bound on consensus latency, proportional to the network delay between the buyer and the seller nodes. Blinkchain selects a random pool of validators, some of which are legitimate with high probability, even when an attacker focuses its forces to crowd out legitimate validators in a small vicinity.

Privacy-Preserving Lawful Contact Chaining

A. Segal; J. Feigenbaum; B. A. Ford 

How can government agencies acquire actionable, useful information about legitimate targets, while preserving the privacy of innocent parties and holding government agencies accountable? Towards understanding this crucial issue, we present the first privacy-preserving protocol for contact chaining, an operation that law-enforcement and intelligence agencies have used effectively. Our experiments suggest that a three-hop, privacy-preserving graph traversal producing 27,000 ciphertexts can be done in under two minutes.

Riffle: An Efficient Communication System With Strong Anonymity

A. Kwon; D. Lazar; S. Devadas; B. A. Ford 

Existing anonymity systems sacrifice anonymity for efficient communication or vice-versa. Onion-routing achieves low latency, high bandwidth, and scalable anonymous communication, but is susceptible to traffic analysis attacks. Designs based on DC-Nets, on the other hand, protect the users against traffic analysis attacks, but sacrifice bandwidth. Verifiable mixnets maintain strong anonymity with low bandwidth overhead, but suffer from high computation overhead instead. In this paper, we present Riffle, a bandwidth and computation efficient communication system with strong anonymity. Riffle consists of a small set of anonymity servers and a large number of users, and guarantees anonymity among all honest clients as long as there exists at least one honest server. Riffle uses a new hybrid verifiable shuffle technique and private information retrieval for bandwidth- and computation-efficient anonymous communication. Our evaluation of Riffle in file sharing and microblogging applications shows that Riffle can achieve a bandwidth of over 100KB/s per user in an anonymity set of 200 users in the case of file sharing, and handle over 100,000 users with less than 10 second latency in the case of microblogging.

Open, privacy-preserving protocols for lawful surveillance

A. Segal; J. Feigenbaum; B. A. Ford 

The question of how government agencies can acquire actionable, useful information about legitimate but unknown targets without intruding upon the electronic activity of innocent parties is extremely important. We address this question by providing experimental evidence that actionable, useful information can indeed be obtained in a manner that preserves the privacy of innocent parties and that holds government agencies accountable. In particular, we present practical, privacy-preserving protocols for two operations that law-enforcement and intelligence agencies have used effectively: set intersection and contact chaining. Experiments with our protocols suggest that privacy-preserving contact chaining can perform a 3-hop privacy-preserving graph traversal producing 27,000 ciphertexts in under two minutes. These ciphertexts are usable in turn via privacy-preserving set intersection to pinpoint potential unknown targets within a body of 150,000 total ciphertexts within 10 minutes, without exposing personal information about non-targets.

AnonRep: Towards Tracking-Resistant Anonymous Reputation

E. Zhai; D. I. Wolinsky; R. Chen; E. Syta; C. Teng et al. 

Reputation systems help users evaluate information quality and incentivize civilized behavior, often by tallying feedback from other users such as “likes” or votes and linking these scores to a user’s long-term identity. This identity linkage enables user tracking, however, and appears at odds with strong privacy or anonymity. This paper presents AnonRep, a practical anonymous reputation system offering the benefits of reputation without enabling long-term tracking. AnonRep users anonymously post messages, which they can verifiably tag with their reputation scores without leaking sensitive information. AnonRep reliably tallies other users’ feedback (e.g., likes or votes) without revealing the user’s identity or exact score to anyone, while maintaining security against score tampering or duplicate feedback. A working prototype demonstrates that AnonRep scales linearly with the number of participating users. Experiments show that the latency for a user to generate anonymous feedback is less than ten seconds in a 10,000-user anonymity group

Building Privacy-Preserving Cryptographic Credentials from Federated Online Identities

J. Maheswaran; D. Jackowitz; E. Zhai; D. I. Wolinsky; B. A. Ford 

Federated identity providers, e.g., Facebook and PayPal, offer a convenient means for authenticating users to third-party applications. Unfortunately such cross-site authentications carry privacy and tracking risks. For example, federated identity providers can learn what applications users are accessing; meanwhile, the applications can know the users’ identities in reality. This paper presents Crypto-Book, an anonymizing layer enabling federated identity authentications while preventing these risks. Crypto-Book uses a set of independently managed servers that employ a (t,n)-threshold cryptosystem to collectively assign credentials to each federated identity (in the form of either a public/private key-pair or blinded signed messages). With the credentials in hand, clients can then leverage anonymous authentication techniques such as linkable ring signatures or partially blind signatures to log into third-party applications in an anonymous yet accountable way. We have implemented a prototype of Crypto-Book and demonstrated its use with three applications: a Wiki system, an anonymous group communication system, and a whistleblower submission system. Crypto-Book is practical and has low overhead: in a deployment within our research group, Crypto-Book group authentication took 1.607s end-to-end, an overhead of 1.2s compared to traditional non-privacy-preserving federated authentication.

Metadata Protection Considerations for TLS Present and Future

B. A. Ford 

TLS 1.3 takes important steps to improve both performance and security, so far offers little protection against traffic analysis or fingerprinting using unencrypted metadata or other side-channels such as transmission lengths and timings. This paper explores metadata protection mechanisms for TLS, including already-included provisions (e.g., record padding), provisions not yet included but potentially feasible in TLS 1.3 (e.g., optional or encrypted headers), and provisions that are likely too ambitious to achieve in TLS 1.3 but may be worth considering for a future “TLS 2.0” (e.g., fully encrypted and authenticated negotiation/handshaking). In addition, we briefly explore how these metadata protection provisions might apply to the datagram-oriented DTLS, or to a version of TLS supporting out-of-order delivery atop TCP.

Keeping Authorities “Honest or Bust” with Decentralized Witness Cosigning

E. Syta; I. Tamas; D. Visher; D. Wolinsky; P. S. Jovanovic et al. 

The secret keys of critical network authorities – such as time, name, certificate, and software update services – represent high-value targets for hackers, criminals, and spy agencies wishing to use these keys secretly to compromise other hosts. To protect authorities and their clients proactively from undetected exploits and misuse, we introduce CoSi, a scalable witness cosigning protocol ensuring that every authoritative statement is validated and publicly logged by a diverse group of witnesses before any client will accept it. A statement S collectively signed by W witnesses assures clients that S has been seen, and not immediately found erroneous, by those W observers. Even if S is compromised in a fashion not readily detectable by the witnesses, CoSi still guarantees S’s exposure to public scrutiny, forcing secrecy-minded attackers to risk that the compromise will soon be detected by one of the W witnesses. Because clients can verify collective signatures efficiently without communication, CoSi protects clients’ privacy, and offers the first transparency mechanism effective against persistent man-inthe-middle attackers who control a victim’s Internet access, the authority’s secret key, and several witnesses’ secret keys. CoSi builds on existing cryptographic multisignature methods, scaling them to support thousands of witnesses via signature aggregation over efficient communication trees. A working prototype demonstrates CoSi in the context of timestamping and logging authorities, enabling groups of over 8,000 distributed witnesses to cosign authoritative statements in under two seconds.

Bitcoin Meets Collective Signing

E. Kokoris Kogias; P. S. Jovanovic; N. Gailly; I. Khoffi; L. Gasser et al. 

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds. ByzCoin achieves Byzantine consensus while preserving Bitcoin’s open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin employs communication trees to optimize transaction commitment and verification under normal operation while guaranteeing safety and liveness under Byzantine faults, up to a near-optimal tolerance of f faulty group members among 3f + 2 total. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. Tree-structured communication further reduces this latency to less than 30 seconds. Due to these optimizations, ByzCoin achieves a throughput higher than PayPal currently handles, with a confirmation latency of 15-20 seconds.

Managing Identities Using Blockchains and CoSi

L. Kokoris-Kogias; L. Gasser; I. Khoffi; P. Jovanovic; N. Gailly et al. 

We combine collective signing and blockchains to create a secure and easy-to-use, decentralized SSH-key management system.

Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing

L. Kokoris-Kogias; P. S. Jovanovic; N. Gailly; I. Khoffi; L. Gasser et al. 

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds. ByzCoin achieves Byzantine consensus while preserving Bitcoin’s open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin employs communication trees to optimize transaction commitment and verification under normal operation while guaranteeing safety and liveness under Byzantine faults, up to a near-optimal tolerance of f faulty group members among 3f + 2 total. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. Tree-structured communication further reduces this latency to less than 30 seconds. Due to these optimizations, ByzCoin achieves a throughput higher than PayPal currently handles, with a confirmation latency of 15-20 seconds.

Private Eyes: Secure Remote Biometric Authentication

E. Syta; M. J. Fischer; D. Wolinsky; A. Silberschatz; G. Gallegos-García et al. 

We propose an efficient remote biometric authentication protocol that gives strong protection to the user’s biometric data in case of two common kinds of security breaches: (1) loss or theft of the user’s token (smart card, handheld device, etc.), giving the attacker full access to any secrets embedded within it; (2) total penetration of the server. Only if both client and server are simultaneously compromised is the user’s biometric data vulnerable to exposure. The protocol works by encrypting the user’s biometric template in a way that allows it to be used for authentication without being decrypted by either token or server. Further, the encrypted template never leaves the token, and only the server has the information that would enable it to be decrypted. We have implemented our protocol using two iris recognition libraries and evaluated its performance. The overall efficiency and recognition performance is essentially the same compared to an unprotected biometric system.

Certificate Cothority: Towards Trustworthy Collective CAs

E. Syta; I. Tamas; D. Visher; D. I. Wolinsky; B. A. Ford 

Deterministically Deterring Timing Attacks in Deterland

W. Wu; B. A. Ford 

The massive parallelism and resource sharing embodying today’s cloud business model not only exacerbate the security challenge of timing channels, but also undermine the viability of defenses based on resource partitioning. We propose hypervisor-enforced timing mitigation to control timing channels in cloud environments. This approach closes “reference clocks” internal to the cloud by imposing a deterministic view of time on guest code, and uses timing mitigators to pace I/O and rate-limit potential information leakage to external observers. Our prototype hypervisor is the first system to mitigate timing-channel leakage across full-scale existing operating systems such as Linux and applications in arbitrary languages. Mitigation incurs a varying performance cost, depending on workload and tunable leakage-limiting parameters, but this cost may be justified for security-critical cloud applications and data.

Seeking Anonymity in an Internet Panopticon

J. Feigenbaum; B. Ford 

Internet, users often need to assume, by default, that their every statement or action online is monitored and tracked. The Dissent project at Yale University takes a collective approach to online anonymity, based on different algorithmic foundations from onion routing, offering concrete advantages, as well as some disadvantages. Dissent preserves maximum security provided only that not all of a group’s servers maliciously collude against their clients. In an honest- security model in which we assume each shuffler correctly follows the protocol the output from the last shuffler offers provable anonymity among all non-colluding clients, provided at least one of the shufflers keeps its random permutation secret. A substantial body of work addresses these vulnerabilities to such active attacks. Dissent addresses the jamming problem by implementing accountability mechanisms, allowing the group to revoke the anonymity of any peer found to be attempting to jam communication maliciously while preserving strong anonymity protection for peers who follow the rules. Dissent now adopts a client/multi-server model with trust split across multiple servers, preferably administered independently. More important in practice, Dissent’s client/multi-server coin-sharing design addresses network churn by making the composition of client ciphertexts independent of the set of other clients online in a given round.

Security Analysis of Accountable Anonymity in Dissent

E. Syta; A. Johnson; H. Corrigan-Gibbs; S-C. Weng; D. Wolinsky et al. 

Users often wish to communicate anonymously on the Internet, for example in group discussion or instant messaging forums. Existing solutions are vulnerable to misbehaving users, however, who may abuse their anonymity to disrupt communication. Dining Cryptographers Networks (DC-nets) leave groups vulnerable to denial-of-service and Sybil attacks, mix networks are difficult to protect against traffic analysis, and accountable voting schemes are unsuited to general anonymous messaging. DISSENT is the first general protocol offering provable anonymity and accountability for moderate-size groups, while efficiently handling unbalanced communication demands among users. We present an improved and hardened DISSENT protocol, define its precise security properties, and offer rigorous proofs of these properties. The improved protocol systematically addresses the delicate balance between provably hiding the identities of well-behaved users, while provably revealing the identities of disruptive users, a challenging task because many forms of misbehavior are inherently undetectable. The new protocol also addresses several non-trivial attacks on the original DISSENT protocol stemming from subtle design flaws.

Heading Off Correlated Failures through Independence-as-a-Service

E. Zhai; R. Chen; D. I. Wolinsky; B. Ford 

Today’s systems pervasively rely on redundancy to ensure reliability. In complex multi-layered hardware/software stacks, however – especially in the clouds where many independent businesses deploy interacting services on common infrastructure – seemingly independent systems may share deep, hidden dependencies, undermining redundancy efforts and introducing unanticipated correlated failures. Complementing existing post-failure forensics, we propose Independence-as-a-Service (or INDaaS), an architecture to audit the independence of redundant systems proactively, thus avoiding correlated failures. INDaaS first utilizes pluggable dependency acquisition modules to collect the structural dependency information (including network, hardware, and software dependencies) from a variety of sources. With this information, INDaaS then quantifies the independence of systems of interest using pluggable auditing modules, offering various performance, precision, and data secrecy tradeoffs. While the most general and efficient auditing modules assume the auditor is able to obtain all required information, INDaaS can employ private set intersection cardinality protocols to quantify the independence even across businesses unwilling to share their full structural information with anyone. We evaluate the practicality of INDaaS with three case studies via auditing realistic network, hardware, and software dependency structures.

Hang With Your Buddies to Resist Intersection Attacks

D. I. Wolinsky; E. Syta; B. Ford 

Some anonymity schemes, such as DC-nets and MIX cascades, can guarantee anonymity even against traffic analysis – provided messages are independent and unlinkable. Users in practice often desire pseudonymity – sending messages intentionally linkable to each other but not to the sender – but pseudonymity in dynamic networks exposes users to intersection attacks. We present Buddies, the first systematic attempt to offer intersection attack resistant pseudonyms in practical anonymity systems. Buddies groups users dynamically into buddy sets, controlling message transmission to make buddies within a set behaviorally indistinguishable to a traffic-monitoring adversary. Intersection attack resistance does not come “for free,” of course, and Buddies offers users control over the inevitable tradeoffs between anonymity, latency, and the useful lifetime of a pseudonym. Using trace-based simulations and a working prototype, we find that Buddies can guarantee non-trivial anonymity set sizes in realistic chat/microblogging scenarios, for both short-lived and long-lived pseudonyms.

Proactively Accountable Anonymous Messaging in Verdict

H. Corrigan-Gibbs; D. I. Wolinsky; B. Ford 

Among anonymity systems, DC-nets have long held attraction for their resistance to traffic analysis attacks, but practical implementations remain vulnerable to internal disruption or “jamming” attacks, which require time-consuming detection procedures to resolve. We present Verdict, the first practical anonymous group communication system built using proactively verifiable DC-nets: participants use public-key cryptography to construct DC-net ciphertexts, and use zero-knowledge proofs of knowledge to detect and exclude misbehavior before disruption. We compare three alternative constructions for verifiable DC-nets: one using bilinear maps and two based on simpler ElGamal encryption. While verifiable DC-nets incur higher computational overheads due to the public-key cryptography involved, our experiments suggest that Verdict is practical for anonymous group messaging or microblogging applications, supporting groups of 100 clients at 1 second per round or 1000 clients at 10 seconds per round. Furthermore, we show how existing symmetric-key DC-nets can “fall back” to a verifiable DC-net to quickly identify misbehavior, speeding up previous detections schemes by two orders of magnitude.

GPUfs: Integrating a File System with GPUs

M. Silberstein; B. Ford; I. Keidar; E. Witchel 

As GPU hardware becomes increasingly general-purpose, it is quickly outgrowing the traditional, constrained GPU-as-coprocessor programming model. To make GPUs easier to program and improve their integration with operating systems, we propose making the host’s file system directly accessible to GPU code. GPUfs provides a POSIX-like API for GPU programs, exploits GPU parallelism for efficiency, and optimizes GPU file access by extending the host CPU’s buffer cache into GPU memory. Our experiments, based on a set of real benchmarks adapted to use our file system, demonstrate the feasibility and benefits of the GPUfs approach. For example, a self-contained GPU program that searches for a set of strings throughout the Linux kernel source tree runs over seven times faster than on an eight-core CPU.

Dissent in Numbers: Making Strong Anonymity Scale

D. I. Wolinsky; H. Corrigan-Gibbs; B. Ford 

Current anonymous communication systems make a trade-off between weak anonymity among many nodes, via onion routing, and strong anonymity among few nodes, via DC-nets. We develop novel techniques in Dissent, a practical group anonymity system, to increase by over two orders of magnitude the scalability of strong, traffic analysis resistant approaches. Dissent derives its scalability from a client/server architecture, in which many unreliable clients depend on a smaller and more robust, but administratively decentralized, set of servers. Clients trust only that at least one server in the set is honest, but need not know or choose which server to trust. Unlike the quadratic costs of prior peer-to-peer DC-nets schemes, Dissent’s client/server design makes communication and processing costs linear in the number of clients, and hence in anonymity set size. Further, Dissent’s servers can unilaterally ensure progress, even if clients respond slowly or disconnect at arbitrary times, ensuring robustness against client churn, tail latencies, and DoS attacks. On DeterLab, Dissent scales to 5,000 online participants with latencies as low as 600 milliseconds for 600-client groups. An anonymous Web browsing application also shows that Dissent’s performance suffices for interactive communication within smaller local-area groups.

Efficient System-Enforced Deterministic Parallelism

A. Aviram; S-C. Weng; S. Hu; B. Ford 

Deterministic execution offers many benefits for debugging, fault tolerance, and security. Current methods of executing parallel programs deterministically, however, often incur high costs, allow misbehaved software to defeat repeatability, and transform time-dependent races into input- or path-dependent races without eliminating them. We introduce a new parallel programming model addressing these issues, and use Determinator, a proof-of-concept OS, to demonstrate the model’s practicality. Determinator’s microkernel API provides only “shared-nothing” address spaces and deterministic interprocess communication primitives to make execution of all unprivileged code—well-behaved or not—precisely repeatable. Atop this microkernel, Determinator’s user-level runtime adapts optimistic replication techniques to offer a private workspace model for both thread-level and process-level parallel programing. This model avoids the introduction of read/write data races, and converts write/write races into reliably-detected conflicts. Coarse-grained parallel benchmarks perform and scale comparably to nondeterministic systems, on both multicore PCs and across nodes in a distributed cluster.

Dissent: Accountable Anonymitous Group Messaging

H. Corrigan-Gibbs; B. Ford 

Users often wish to participate in online groups anonymously, but misbehaving users may abuse this anonymity to disrupt the group. Messaging protocols such as Mix-nets and DC-nets leave online groups vulnerable to denial-of-service and Sybil attacks, while accountable voting protocols are unusable or inefficient for general anonymous messaging. We present the first general messaging protocol that offers provable anonymity with accountability for moderate-size groups, and efficiently handles unbalanced loads where few members have much data to transmit in a given round. The N group members first cooperatively shuffle an N x N matrix of pseudorandom seeds, then use these seeds in N “pre-planned” DC-nets protocol runs. Each DC-nets run transmits the variable-length bulk data comprising one member’s message, using the minimum number of bits required for anonymity under our attack model. The protocol preserves message integrity and one-to-one correspondence between members and messages, makes denial-of-service attacks by members traceable to the culprit, and efficiently handles large and unbalanced message loads. A working prototype demonstrates the protocol’s practicality for anonymous messaging in groups of 40+ member nodes.

Delegative Democracy

B. A. Ford 

Delegative democracy is a new paradigm for democratic organization which emphasizes individually chosen vote transfers (“delegation”) over mass election. Delegative democracy combines the best elements of direct and representative democracy by replacing artificially imposed representation structures with an adaptive structure founded on real personal and group trust relationships. Delegative democracy empowers individuals and encourages widespread direct participation in a democratic organization, without unduly burdening or disenfranchising those members who, for lack of time, interest, or knowledge, would prefer to take a more passive role.