Event
Ph.D. Research Proposal Exam: Georgios Tsimos
Tuesday, April 2, 2024
1:00 p.m.
(Online) https://umd.zoom.us/j/92441300909
Maria Hoo
301 405 3681
mch@umd.edu
ANNOUNCEMENT: Ph.D. Research Proposal Exam
Name: Georgios Tsimos
Committee:
Professor Jonathan Katz (Chair)
Professor Dana Dachman-Soled
Professor Tudor Dumitraş
Date/time: April 2, 2024 at 1pm
Location: (Online) https://umd.zoom.us/j/92441300909
Title: Improving Round and Communication Metrics in Consensus
Abstract:
Byzantine Consensus protocols, aka Byzantine Agreement (BA), Byzantine Broadcast (BB), allow a set of n mutually distrusting parties to share input values and agree on the same output value. Notable practical applications of consensus in blockchains and MPC require efficient practical consensus protocols. To this end, in this research proposal we explore directions towards improving the two major metrics of efficiency of such protocols; i.e. their communication and round complexities.
In CRYPTO’22, we deployed gossiping techniques to provide randomized (Parallel) BB protocols with improved communication complexity, against both static and adaptive adversaries who can control the majority of participants. Namely, we proposed the first synchronous Parallel BB protocol against t < (1 − ε)n adaptive corruptions, with quadratic communication complexity. In a different result of the same paper, we provide an alternative protocol, in case fewer trust assumptions are preferable.
In SODA’24, we showed the first synchronous deterministic strong BA protocol with O(n·f) adaptive communication complexity against an adaptive adversary, where f is the runtime number of corruptions. Our protocol incurs subquadratic communication in cases where the runtime number of corruptions is o(n), even if the corruption threshold t is O(n); in that case, the previous best-known result required quadratic communication independently of f.
Our results so far tackle communication complexity. In order to more holistically improve the practicality of consensus protocols, we propose to further attack research questions related to different aspects of efficiency such as: 1) improving the round complexity of synchronous BB protocols, 2) rendering communication-efficient BB protocols more practical and, 3) improving the concrete efficiency of existing deployed consensus protocols, also in asynchronous or partially synchronous settings.
