The second workshop for partners focuses on the work of doctoral students. The programme is as follows:

17h00 : Introduction
              Petr Kuznetsov, Professeur, Télécom Paris, Institut Polytechnique de Paris.

17h10 : How to Tame Multiple Spending in Decentralized Cryptocurrencies,
Joao Paulo Bezerra De Araujo, Doctorant, Télécom Paris, Institut Polytechnique de Paris.

Abstract : The last decade has seen a variety of Asset-Transfer systems designed for decentralized environments. To address the problem of double-spending, these systems inherently make strong model assumptions and spend a lot of resources. We take a non-orthodox approach to the double-spending problem that might suit better realistic environments in which these systems are to be deployed. We consider the decentralized trust setting, where each user may independently choose who to trust by forming their local quorums. In this setting, we define k-Spending Asset Transfer, a relaxed version of asset transfer which bounds the number of times the same asset can be spent. We establish a precise relationship between the decentralized trust assumptions and k, the optimal spending number of the system.

Publications :

João Paulo Bezerra de Araújo, Petr Kuznetsov and Alice Koroleva. “Relaxed Reliable Broadcast for Decentralized Trust”. NETYS 2022

João Paulo Bezerra, Petr Kuznetsov: “Brief Announcement: How to Tame Multiple Spending in Decentralized Cryptocurrencie”s. PODC 2022

17h30 : Byzantine fault-tolerant distributed computing without consensus,
Andrei Tonkikh, Doctorant, Télécom Paris, Institut Polytechnique de Paris.

Abstract : Consensus is the central problem in distributed computing. However, it is also known to be a hard problem, with a number of harsh lower bounds on its performance and even an impossibility proof for asynchronous message-passing systems. Hence, it is an important question whether a particular problem is solvable without consensus. In this talk, I will focus on two specific problems: distributed random number generation and asset transfer systems.

With a simple modification of a famous theorem, we demonstrate that perfect distributed random generation is, indeed, impossible in an asynchronous system without consensus. To circumvent this impossibility, we introduce several relaxations of the problem and provide algorithms efficiently solving these relaxations. We further study potential applications.

Asset transfer is known to be solvable in asynchronous systems without consensus as long as each account is controlled by a single user and is never accessed concurrently. However, not only this prohibits the typical use-cases of sharing an account with relatives or within a company, but it also introduces an extremely high cost for accidentally trying to issue two concurrent transactions. For example, as a result of using two mobile devices. To address this issue, we introduce a hybrid system that does not rely on consensus in the common case but is capable of recovering with the help of consensus in the bad case when multiple concurrent transactions are issued on the same account. Furthermore, we manage to fall back to consensus only in extremely unlikely cases when the sum of the concurrent transactions exceeds the account balance.

Publications :

Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, Andrei Tonkikh. “Permissionless and Asynchronous Asset Transfer”, DISC 2021: 28:1-28:19

Luciano Freitas de Souza, Petr Kuznetsov, Andrei Tonkikh. “Asynchronous Randomness and Consensus without Trusted Setup”, DISC 2022

17h50 : Conclusion