Mirror worlds, eclipse attacks and the security of Bitcoin and the RPKI

While distributed databases offer great promise their decentralized nature poses a number of security and privacy issues. In what ways can parties misbehave? If a database is truly distributed can a malicious actor hide their misdeeds by presenting conflicting views of the database? Can we overcome such deceit and either prevent it by eliminating trust assumptions or detect such perfidy and hold the malicious party to account? We study these questions across two distributed databases: RPKI (Resource Public Key Infrastructure), which is used to authenticate the allocation and announcement of IP prefixes; and Bitcoin, a cryptocurrency that utilizes a permissionless database called a blockchain to track the transfer and ownership of bitcoins. The first part of this dissertation focuses on RPKI and the potential of RPKI authorities to misbehave. We consider the methods, motivations, and impact of this misbehavior and how an RPKI authority can present inconsistent views to hide this misbehavior. After studying the problem we propose solutions to detect and identify such misbehavior. Now we turn our attention to Bitcoin. We look at ways an attacker can manipulate Bitcoin's Peer-to-Peer network to cause members of the network to have inconsistent views of Bitcoin's blockchain and subvert Bitcoin's core security guarantees. We then propose countermeasures to harden Bitcoin against such attacks. The final part of this dissertation discusses the problem of privacy in Bitcoin. Many of the protocols developed to address Bitcoin's privacy limitations introduce trusted parties. We instead design privacy enhancing protocols that use an untrusted intermediary to mix \aka anonymize, bitcoin transactions via blind signatures. To do this we must invent a novel blind signature fair-exchange protocol that runs on Bitcoin's blockchain. This dissertation favors a dirty slate design process. We work to layer protections on existing protocols and when we must make changes to the underlying protocol we carefully weigh compatibility and deployment considerations. This philosophy has resulted in some of the research described in this dissertation influencing the design of deployed protocols. In the case of Bitcoin our research is currently used to harden a network controlling approximately a trillion dollars