Muneeb Ali is presenting his Pre FPO on Thursday, June 30, 2016 at 3pm in CS 402. The members of his committee are Andrea LaPaugh (advisor), Mike Freedman (reader), Arvind Narayanan (reader), Jen Rexford (non-reader), and Brian Kernighan (non-reader). Title and abstract follow below: Title: "Bootstrapping Trust in Distributed Systems with Blockchains" Abstract: Blockchains like Bitcoin and Ethereum have seen significant adoption in the past few years. Beyond their cryptocurrency uses, blockchains are being used to build new, decentralized versions of DNS and public-key infrastructure (PKI) that have no central points of trust. Blockchains can provide the basis for a general-purpose "trust layer" for Internet applications, but certain aspects of contemporary blockchains present technical limitations. Blockchains are hard to modify after initial deployment, they cannot store much data, they have slow writes (order of minutes), and the time to bootstrap new nodes increases linearly every day. Further, little production data or experience is available to guide design tradeoffs. In this thesis, we present the design of a new blockchain-based naming and storage system called Blockstack. Blockstack solves several limitations of contemporary blockchains and its design is informed by our experience of operating a large deployment of a decentralized PKI service built on top of the Namecoin blockchain. Our production deployment led to the discovery of a critical security problem on the Namecoin network along with highlighting network reliability and throughput challenges, while registering and updating over 33,000 entries. We present the design of (a) a migration framework for migrating from one blockchain to another under a failure of the underlying blockchain — our migration from Namecoin to Bitcoin used this framework and is the first crosschain migration of a production system running on blockchains, (b) a logically separate layer, virtualchain, which introduces novel new functionality to production blockchains without requiring any consensus-breaking changes from the underlying blockchain, and (c) a decentralized storage mechanism that is resistant to sybil-attacks. Blockstack is used as a general-purpose "trust layer" by a variety of applications/services, including a production PKI system for 57,000 users that has no single point of trust/failure and a large decentralized marketplace. Blockstack is released as open source software (http://github.com/blockstack).