Multiparty Computation Protocols Based on Cryptocurrencies

Niniejsza praca przedstawia wykorzystanie walut kryptograficznych (głównie Bitcoina) oraz technik wywodzących się z walut kryptograficznych do konstrukcji protokołów do obliczeń wielopodmiotowych (ang. Multiparty Computation Protocols, MPC), które wychodzą poza standardową definicję bezpieczeństwa protokołów MPC.W pierwszej części pracy analizujemy protokoły MPC, w których strony mają dostęp do kryptowaluty w stylu Bitcoina. Pokazujemy przy tym założeniu konstrukcję protokołu MPC dla dwóch stron do obliczania wartości dowolnej funkcji f, który ma dwie zalety w stosunku do klasycznych protokołów MPC. Po pierwsze, klasyczne protokoły MPC dla dwóch stron nie gwarantują tzw. sprawiedliwości obliczeń (ang. fairness), co oznacza, że nieuczciwa strona może przerwać wykonanie protokołu w stanie, w którym jedynie ona zna wynik obliczenia. W odróżnieniu od standardowych protokołów MPC, nasz protokół zapewnia pewien rodzaj sprawiedliwości obliczeń. Dokładniej, strona, która nie pozna wyniku obliczenia, automatycznie otrzymuje rekompensatę finansową. Ponadto, wartość funkcji f może zawierać instrukcje w stylu "Strona A płaci 1 bitcoina stronie B" i nasz protokół gwarantuje, że takie przelewy zostaną automatycznie wykonane. Pozwala to zatem na konstrukcje protokołów z konsekwencjami finansowymi. W pracy przedstawiamy również metody formalnej weryfikacji poprawności i bezpieczeństwa tego typu protokołów oraz pokazujemy w jaki sposób chronić te protokoły przed tzw. kowalnością (ang. malleability) transakcji, która jest problemem występującym w większości kryptowalut.Ponadto analizujemy protokoły kryptograficzne w sieciach peer-to-peer, które nie wymagają infrastruktury klucza publicznego ani źródła skorelowanej losowości (ang. random beacon) przy założeniu ograniczonej mocy obliczeniowej przeciwnika. Pokazujemy, że każda funkcjonalność, która może zostać zrealizowana przy założeniu, że większość stron wykonujących protokół jest uczciwa i dostępna jest infrastruktura klucza publicznego może zostać również zrealizowana przy założeniu, że większość mocy obliczeniowej jest uczciwa bez założenia o istnieniu infrastruktury klucza publicznego.

In this dissertation we show how to use cryptocurrencies (mostly Bitcoin) and techniques coming from the field of cryptocurrencies to construct new types of Multiparty Computation Protocols (MPC), which go beyond the standard definition of MPC.In the first part of the dissertation we study the MPC protocols, in which parties have access to a Bitcoin-like cryptocurrency. We show that in this setting it is possible to design a two-party MPC protocol for computing a value of an arbitrary function f that has two advantages over classical MPC protocols. First, classical two-party MPC protocols do not guarantee fairness, which means that a malicious party can interrupt the execution of a protocol in a state, in which he/she knows the output of the protocol, but the other party does not. In contrast, our MPC protocol do guarantee some kind of fairness. More precisely, a party who has not learnt the output due to the other party’s misbehaviour is given a financial compensation. Moreover, the value of the function f being computed can contain instructions like “The party A pays 1 bitcoin to the party B” and our protocol guarantees that such transfers will automatically take place. Therefore, it allows to create two-party protocols with financial consequences. We also discuss how to formally verify the correctness and the security of such protocols and show how to protect them against the so-called malleability of transactions, which is a problem concerning most cryptocurrencies.Then, we study cryptographic protocols in a fully peer-to-peer scenario under the assumption that the computing power of the adversary is limited and there is no trusted setup (like a PKI or an unpredictable beacon). We show that every primitive (e.g. Byzantine consensus) that can be realised under the classical assumption that the majority of the parties executing the protocol is honest and there is a PKI available can also be realised under the assumption that the majority of the computing power is controlled by honest parties and there is no PKI.