On the (im)possibility of building off-chain protocols from minimal assumptions

Blockchains have come a long way since the introduction of Bitcoin in 2008. Cryptocurrencies have become a household name as more people and even countries see the appeal in a secure decentralized ledger capable of processing monetary transactions and executing programs. Yet, one of the drawbacks of such decentralized systems is their lack of scalability. Hence, blockchains are unfortunately not ready to replace the existing financial system or cost-effectively execute programs. One class of solutions, proposed to tackle these limitations, are off-chain protocols. These protocols shift the communication away from the blockchain, by allowing parties to mostly communicate directly with each another. This direct communication is also referred to as off-chain communication. Probably the most well-known off-chain solution developed to date are Payment Channel Networks (PCNs). PCNs allow parties to make monetary transactions off-chain. Recently, more advanced off-chain solutions such as virtual channels, state channels and Plasma protocols have been developed for the Ethereum blockchain. These solutions allow making payments with improved efficiency and even executing programs (called smart contracts) off-chain. However, they rely on the fact that the Ethereum blockchain can execute Turing complete smart contracts, and it was unclear if one can build such protocols over more restricted blockchains such as Bitcoin. In this thesis, we start by showing that virtual and state channels can be built over Bitcoin and similar blockchains. First, we present a new channel solution called generalized channels over Bitcoin. Generalized channels are comparable to state channels over Ethereum, i.e., generalized channels allow parties to execute applications off-chain that are supported by the underlying blockchain. In order to design generalized channels, we formalized a new primitive called adaptor signatures for the first time and show that Schnorr and ECDSA instantiations of this primitive are secure in our model. We then show that virtual channels can also be built over Bitcoin and Bitcoin-like blockchains. Virtual channels improve the efficiency of PCNs by reducing the communication needed for making off-chain payments. We further analyze the security of our protocols in the Universal Composability framework of Cannetti. We continue by extending our adaptor signature formalization and model two-party adaptor signatures. This extension helps improve the efficiency of our generalized channel construction. We provide two generic transformations that allow us to instantiate single and two-party adaptor signature schemes from signature schemes built from identification schemes that satisfy certain properties. We show that the Schnorr, Katz-Wang, and Guillou-Quisquater signature schemes satisfy the necessary properties required by our transformations and can generically be transformed into single and two-party adaptor signatures. Finally, we show that it is impossible to transform unique signatures schemes such as BLS into adaptor signature schemes. After showing how to instantiate generalized and virtual channels over more restricted blockchains such as Bitcoin, we turn our attention to an alternative off-chain protocol called Plasma. In this solution, a single operator is responsible for updating parties' balances off-chain according to their transactions. On a high level, there are two classes of Plasma protocols, Plasma Cash and Plasma MVP, each with its advantages and disadvantages. Many in the Ethereum community focused on building a protocol that inherits the best properties of both classes without suffering from their disadvantages. We show that it is impossible to build a protocol that achieves the best of both worlds. Put differently, there is an inherent separation between Plasma Cash and MVP. This result can also be seen as "bringing order'' to the huge landscape of Plasma protocols discussed in the Ethereum community. We further provide a formal model for Plasma protocols and also present instantiations of Plasma Cash and MVP that are secure in our model. Finally, we conclude this thesis by presenting CommiTEE, an efficient yet simple Plasma protocol using a Trusted Execution Environment (TEE). A TEE is a piece of hardware that guarantees the correct execution of programs and secure storage of secret values. We only require the operator to have access to a TEE, and hence the end users are not burdened with purchasing expensive equipment. Our protocol removes many of the drawbacks seen in other Plasma constructions and offers a practical solution for real-world usage