Jovan Komatovic
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Jovan Komatovic has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Muhammad Ayaz Dzulfikar
National University of Singapore, Singapore, Singapore
2 shared publications - Rachid Guerraoui
EPFL
2 shared publications - Seth Gilbert
National University of Singapore, Singapore, Singapore
2 shared publications - Vincent Gramoli
University of Sydney, Sydney, Australia
2 shared publications - Yuval Efron
Columbia University
2 shared publications - Daniel Collins
EPFL
1 shared publication
Latest Publications
- 28 April 2025
- Published by Springer Nature
- p. 65-95
Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
- 28 April 2025
- Published by Springer Nature
- p. 65-95
Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
- Open Access
Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $t<n/2$ corruptions, bypassing the setup-free $t<n/3$ barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher corruption resilience ($n/2$ instead of $n/3$) for the price of increased assumptions. Is this trade-off necessary? We further the study of crypto-agnostic Byzantine agreement among $n$ parties that answers this question in the negative. Specifically, let $t_s$ and $t_i$ denote two parameters such that (1) $2t_i + t_s < n$, and (2) $t_i \leq t_s < n/2$. Crypto-agnostic Byzantine agreement ensures agreement among honest parties if (1) the adversary is computationally bounded and corrupts up to $t_s$ parties, or (2) the adversary is computationally unbounded and corrupts up to $t_i$ parties, and is moreover given all secrets of all parties established during the setup. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols in the authenticated and information-theoretic setting into one that is crypto-agnostic. Our compiler has several attractive qualities, including using only $O(λn^2)$ bits over the two underlying Byzantine agreement protocols, and preserving round and communication complexity in the authenticated setting. In particular, our results improve the state-of-the-art in bit complexity by at least two factors of $n$ and provide either early stopping (deterministic) or expected constant round complexity (randomized). We therefore provide fallback security for authenticated Byzantine agreement for free for $t_i \leq n/4$.Open AccessJuggernaut: Efficient Crypto-Agnostic Byzantine Agreement
It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $t<n/2$ corruptions, bypassing the setup-free $t<n/3$ barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher corruption resilience ($n/2$ instead of $n/3$) for the price of increased assumptions. Is this trade-off necessary? We further the study of crypto-agnostic Byzantine agreement among $n$ parties that answers this question in the negative. Specifically, let $t_s$ and $t_i$ denote two parameters such that (1) $2t_i + t_s < n$, and (2) $t_i \leq t_s < n/2$. Crypto-agnostic Byzantine agreement ensures agreement among honest parties if (1) the adversary is computationally bounded and corrupts up to $t_s$ parties, or (2) the adversary is computationally unbounded and corrupts up to $t_i$ parties, and is moreover given all secrets of all parties established during the setup. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols in the authenticated and information-theoretic setting into one that is crypto-agnostic. Our compiler has several attractive qualities, including using only $O(λn^2)$ bits over the two underlying Byzantine agreement protocols, and preserving round and communication complexity in the authenticated setting. In particular, our results improve the state-of-the-art in bit complexity by at least two factors of $n$ and provide either early stopping (deterministic) or expected constant round complexity (randomized). We therefore provide fallback security for authenticated Byzantine agreement for free for $t_i \leq n/4$. - Open Access
- 11 December 2023
- Published by Springer Nature in Distributed Computing
- Vol. 37 (2) , 89-119
Byzantine consensus is $\Theta (n^2)$: the Dolev-Reischuk bound is tight even in partial synchrony!The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system withnprocesses and at most $$f < n / 3$$ failures, any solution to Byzantine consensus exchanges $$\Omega \big (n^2\big )$$ words, where a word contains a constant number of values and signatures. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony where the network alternates between (1) asynchronous periods, with unbounded message delays, and (2) synchronous periods, with $$\delta $$ -bounded message delays. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducingSQuad, a partially synchronous Byzantine consensus protocol with $$O\big (n^2\big )$$ worst-case communication complexity. In addition,SQuadis optimally-resilient (tolerating up to $$f < n / 3$$ failures) and achieves $$O(f \cdot \delta )$$ worst-case latency complexity. The key technical contribution underlyingSQuadlies in the way we solveview synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we presentRareSync, a view synchronization protocol with $$O\big (n^2\big )$$ communication complexity and $$O(f \cdot \delta )$$ latency complexity, which we utilize in order to obtainSQuad.- 11 December 2023
- Published by Springer Nature in Distributed Computing
- Vol. 37 (2) , 89-119
Open AccessByzantine consensus is $\Theta (n^2)$: the Dolev-Reischuk bound is tight even in partial synchrony!The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system withnprocesses and at most $$f < n / 3$$ failures, any solution to Byzantine consensus exchanges $$\Omega \big (n^2\big )$$ words, where a word contains a constant number of values and signatures. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony where the network alternates between (1) asynchronous periods, with unbounded message delays, and (2) synchronous periods, with $$\delta $$ -bounded message delays. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducingSQuad, a partially synchronous Byzantine consensus protocol with $$O\big (n^2\big )$$ worst-case communication complexity. In addition,SQuadis optimally-resilient (tolerating up to $$f < n / 3$$ failures) and achieves $$O(f \cdot \delta )$$ worst-case latency complexity. The key technical contribution underlyingSQuadlies in the way we solveview synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we presentRareSync, a view synchronization protocol with $$O\big (n^2\big )$$ communication complexity and $$O(f \cdot \delta )$$ latency complexity, which we utilize in order to obtainSQuad. - Open Access
- 2 February 2023
- Published by Springer Nature in Research Square
Byzantine Consensus is Θ(n2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!
The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.
- 2 February 2023
- Published by Springer Nature in Research Square
Open AccessByzantine Consensus is Θ(n2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!
The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.