13 Search Results for "Nayak, Kartik"

Document
DOI: 10.4230/LIPIcs.DISC.2024.30
Granular Synchrony

Authors: Neil Giridharan, Ittai Abraham, Natacha Crooks, Kartik Nayak, and Ling Ren

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
Today’s mainstream network timing models for distributed computing are synchrony, partial synchrony, and asynchrony. These models are coarse-grained and often make either too strong or too weak assumptions about the network. This paper introduces a new timing model called granular synchrony that models the network as a mixture of synchronous, partially synchronous, and asynchronous communication links. The new model is not only theoretically interesting but also more representative of real-world networks. It also serves as a unifying framework where current mainstream models are its special cases. We present necessary and sufficient conditions for solving crash and Byzantine fault-tolerant consensus in granular synchrony. Interestingly, consensus among n parties can be achieved against f ≥ n/2 crash faults or f ≥ n/3 Byzantine faults without resorting to full synchrony.
Cite as

Neil Giridharan, Ittai Abraham, Natacha Crooks, Kartik Nayak, and Ling Ren. Granular Synchrony. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{giridharan_et_al:LIPIcs.DISC.2024.30,
  author =	{Giridharan, Neil and Abraham, Ittai and Crooks, Natacha and Nayak, Kartik and Ren, Ling},
  title =	{{Granular Synchrony}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{30:1--30:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.30},
  URN =		{urn:nbn:de:0030-drops-212566},
  doi =		{10.4230/LIPIcs.DISC.2024.30},
  annote =	{Keywords: Timing model, synchrony, asynchrony, consensus, blockchain, fault tolerance}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.24
Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

Authors: Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Agreement protocols for partially synchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. In particular, we show a version of HotStuff that retains linear communication complexity in each view, leveraging trusted hardware to tolerate a minority of corruptions. Our result uses expander graph techniques to achieve efficient communication in a manner that may be of independent interest.
Cite as

Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter. Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{yandamuri_et_al:LIPIcs.OPODIS.2022.24,
  author =	{Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael K.},
  title =	{{Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.24},
  URN =		{urn:nbn:de:0030-drops-176448},
  doi =		{10.4230/LIPIcs.OPODIS.2022.24},
  annote =	{Keywords: communication complexity, consensus, trusted hardware}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.5
Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization

Authors: Ittai Abraham, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper studies the good-case latency of unauthenticated Byzantine fault-tolerant broadcast, which measures the time it takes for all non-faulty parties to commit given a non-faulty broadcaster. For both asynchrony and synchrony, we show that n ≥ 4f is the tight resilience threshold that separates good-case 2 rounds and 3 rounds. For asynchronous Byzantine reliable broadcast (BRB), we also investigate the bad-case latency for all non-faulty parties to commit when the broadcaster is faulty but some non-faulty party commits. We provide matching upper and lower bounds on the resilience threshold of bad-case latency for BRB protocols with optimal good-case latency of 2 rounds. In particular, we show 2 impossibility results and propose 4 asynchronous BRB protocols.
Cite as

Ittai Abraham, Ling Ren, and Zhuolun Xiang. Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2021.5,
  author =	{Abraham, Ittai and Ren, Ling and Xiang, Zhuolun},
  title =	{{Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.5},
  URN =		{urn:nbn:de:0030-drops-157806},
  doi =		{10.4230/LIPIcs.OPODIS.2021.5},
  annote =	{Keywords: Byzantine broadcast, asynchrony, synchrony, latency, good-case, optimal}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.7
Twins: BFT Systems Made Robust

Authors: Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper presents Twins, an automated unit test generator of Byzantine attacks. Twins implements three types of Byzantine behaviors: (i) leader equivocation, (ii) double voting, and (iii) losing internal state such as forgetting "locks" guarding voted values. To emulate interesting attacks by a Byzantine node, it instantiates twin copies of the node instead of one, giving both twins the same identities and network credentials. To the rest of the system, the twins appear indistinguishable from a single node behaving in a "questionable" manner. Twins can systematically generate Byzantine attack scenarios at scale, execute them in a controlled manner, and examine their behavior. Twins scenarios iterate over protocol rounds and vary the communication patterns among nodes. Twins runs in a production setting within DiemBFT where it can execute 44M Twins-generated scenarios daily. Whereas the system at hand did not manifest errors, subtle safety bugs that were deliberately injected for the purpose of validating the implementation of Twins itself were exposed within minutes. Twins can prevent developers from regressing correctness when updating the codebase, introducing new features, or performing routine maintenance tasks. Twins only requires a thin wrapper over DiemBFT, we thus envision other systems using it. Building on this idea, one new attack and several known attacks against other BFT protocols were materialized as Twins scenarios. In all cases, the target protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems.
Cite as

Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi. Twins: BFT Systems Made Robust. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 7:1-7:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bano_et_al:LIPIcs.OPODIS.2021.7,
  author =	{Bano, Shehar and Sonnino, Alberto and Chursin, Andrey and Perelman, Dmitri and Li, Zekun and Ching, Avery and Malkhi, Dahlia},
  title =	{{Twins: BFT Systems Made Robust}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{7:1--7:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.7},
  URN =		{urn:nbn:de:0030-drops-157825},
  doi =		{10.4230/LIPIcs.OPODIS.2021.7},
  annote =	{Keywords: Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.27
Optimal Good-Case Latency for Rotating Leader Synchronous BFT

Authors: Ittai Abraham, Kartik Nayak, and Nibesh Shrestha

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper explores the good-case latency of synchronous Byzantine Fault Tolerant (BFT) consensus protocols in the rotating leader setting. We first present a lower bound that relates the latency of a broadcast when the sender is honest and the latency of switching to the next sender. We then present a matching upper bound with a latency of 2Δ (Δ is the pessimistic synchronous delay) with an optimistically responsive change to the next sender. The results imply that both our lower and upper bounds are tight. We implement and evaluate our protocol and show that our protocol obtains similar latency compared to state-of-the-art stable-leader protocol Sync HotStuff while allowing optimistically responsive leader rotation.
Cite as

Ittai Abraham, Kartik Nayak, and Nibesh Shrestha. Optimal Good-Case Latency for Rotating Leader Synchronous BFT. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2021.27,
  author =	{Abraham, Ittai and Nayak, Kartik and Shrestha, Nibesh},
  title =	{{Optimal Good-Case Latency for Rotating Leader Synchronous BFT}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.27},
  URN =		{urn:nbn:de:0030-drops-158022},
  doi =		{10.4230/LIPIcs.OPODIS.2021.27},
  annote =	{Keywords: Distributed Computing, Byzantine Fault Tolerance, Synchrony}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.46
Brief Announcement: Twins – BFT Systems Made Robust

Authors: Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Twins is an effective strategy for generating test scenarios with Byzantine [Lamport et al., 1982] nodes in order to find flaws in Byzantine Fault Tolerant (BFT) systems. Twins finds flaws in the design or implementation of BFT protocols that may cause correctness issues. The main idea of Twins is the following: running twin instances of a node that use correct, unmodified code and share the same network identity and credentials allows to emulate most interesting Byzantine behaviors. Because a twin executes normal, unmodified node code, building Twins only requires a thin wrapper over an existing distributed system designed for Byzantine tolerance. To emulate material, interesting scenarios with Byzantine nodes, it instantiates one or more twin copies of the node, giving the twins the same identities and network credentials as the original node. To the rest of the system, the node and all its twins appear indistinguishable from a single node behaving in a "questionable" manner. This approach generates many interesting Byzantine behaviors, including equivocation, double voting, and losing internal state, while forgoing uninteresting behavior scenarios that can be filtered at the transport layer, such as producing semantically invalid messages. Building on configurations with twin nodes, Twins systematically generates scenarios with Byzantine nodes via enumeration over protocol rounds and communication patterns among nodes. Despite this being inherently exponential, one new flaw and several known flaws were materialized by Twins in the arena of BFT consensus protocols. In all cases, protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems. In two of these cases, it took the community more than a decade to discover protocol flaws that Twins would have surfaced within minutes. Additionally, Twins has been incorporated into the continuous release testing process of a production setting (DiemBFT) in which it can execute 44M Twins-generated scenarios daily.
Cite as

Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi. Brief Announcement: Twins – BFT Systems Made Robust. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 46:1-46:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bano_et_al:LIPIcs.DISC.2021.46,
  author =	{Bano, Shehar and Sonnino, Alberto and Chursin, Andrey and Perelman, Dmitri and Li, Zekun and Ching, Avery and Malkhi, Dahlia},
  title =	{{Brief Announcement: Twins – BFT Systems Made Robust}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{46:1--46:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.46},
  URN =		{urn:nbn:de:0030-drops-148485},
  doi =		{10.4230/LIPIcs.DISC.2021.46},
  annote =	{Keywords: Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.62
Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

Authors: Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael Reiter

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Small trusted hardware primitives can improve fault tolerance of Byzantine Fault Tolerant (BFT) protocols to one-half faults. However, existing works achieve this at the cost of increased communication complexity. In this work, we explore the design of communication-efficient BFT protocols that can boost fault tolerance to one-half without worsening communication complexity. Our results include a version of HotStuff that retains linear communication complexity in each view and a version of the VABA protocol with quadratic communication, both leveraging trusted hardware to tolerate a minority of corruptions. As a building block, we present communication-efficient provable broadcast, a core broadcast primitive with increased fault tolerance. Our results use expander graphs to achieve efficient communication in a manner that may be of independent interest.
Cite as

Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael Reiter. Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yandamuri_et_al:LIPIcs.DISC.2021.62,
  author =	{Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael},
  title =	{{Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{62:1--62:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.62},
  URN =		{urn:nbn:de:0030-drops-148647},
  doi =		{10.4230/LIPIcs.DISC.2021.62},
  annote =	{Keywords: communication complexity, consensus, trusted hardware}
}
Document
DOI: 10.4230/LIPIcs.ITC.2021.8
Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions

Authors: T-H. Hubert Chan, Elaine Shi, Wei-Kai Lin, and Kartik Nayak

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract
Oblivious RAM (ORAM) is a technique for compiling any RAM program to an oblivious counterpart, i.e., one whose access patterns do not leak information about the secret inputs. Similarly, Oblivious Parallel RAM (OPRAM) compiles a parallel RAM program to an oblivious counterpart. In this paper, we care about ORAM/OPRAM with perfect security, i.e., the access patterns must be identically distributed no matter what the program’s memory request sequence is. In the past, two types of perfect ORAMs/OPRAMs have been considered: constructions whose performance bounds hold in expectation (but may occasionally run more slowly); and constructions whose performance bounds hold deterministically (even though the algorithms themselves are randomized). In this paper, we revisit the performance metrics for perfect ORAM/OPRAM, and show novel constructions that achieve asymptotical improvements for all performance metrics. Our first result is a new perfectly secure OPRAM scheme with O(log³ N/log log N) expected overhead. In comparison, prior literature has been stuck at O(log³ N) for more than a decade. Next, we show how to construct a perfect ORAM with O(log³ N/log log N) deterministic simulation overhead. We further show how to make the scheme parallel, resulting in an perfect OPRAM with O(log⁴ N/log log N) deterministic simulation overhead. For perfect ORAMs/OPRAMs with deterministic performance bounds, our results achieve subexponential improvement over the state-of-the-art. Specifically, the best known prior scheme incurs more than √N deterministic simulation overhead (Raskin and Simkin, Asiacrypt'19); moreover, their scheme works only for the sequential setting and is not amenable to parallelization. Finally, we additionally consider perfect ORAMs/OPRAMs whose performance bounds hold with high probability. For this new performance metric, we show new constructions whose simulation overhead is upper bounded by O(log³ /log log N) except with negligible in N probability, i.e., we prove high-probability performance bounds that match the expected bounds mentioned earlier.
Cite as

T-H. Hubert Chan, Elaine Shi, Wei-Kai Lin, and Kartik Nayak. Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ITC.2021.8,
  author =	{Chan, T-H. Hubert and Shi, Elaine and Lin, Wei-Kai and Nayak, Kartik},
  title =	{{Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.8},
  URN =		{urn:nbn:de:0030-drops-143271},
  doi =		{10.4230/LIPIcs.ITC.2021.8},
  annote =	{Keywords: perfect oblivious RAM, oblivious PRAM}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.25
Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP

Authors: Shir Cohen, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
King and Saia were the first to break the quadratic word complexity bound for Byzantine Agreement in synchronous systems against an adaptive adversary, and Algorand broke this bound with near-optimal resilience (first in the synchronous model and then with eventual-synchrony). Yet the question of asynchronous sub-quadratic Byzantine Agreement remained open. To the best of our knowledge, we are the first to answer this question in the affirmative. A key component of our solution is a shared coin algorithm based on a VRF. A second essential ingredient is VRF-based committee sampling, which we formalize and utilize in the asynchronous model for the first time. Our algorithms work against a delayed-adaptive adversary, which cannot perform after-the-fact removals but has full control of Byzantine processes and full information about communication in earlier rounds. Using committee sampling and our shared coin, we solve Byzantine Agreement with high probability, with a word complexity of Õ(n) and O(1) expected time, breaking the O(n²) bit barrier for asynchronous Byzantine Agreement.
Cite as

Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.DISC.2020.25,
  author =	{Cohen, Shir and Keidar, Idit and Spiegelman, Alexander},
  title =	{{Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.25},
  URN =		{urn:nbn:de:0030-drops-131034},
  doi =		{10.4230/LIPIcs.DISC.2020.25},
  annote =	{Keywords: shared coin, Byzantine Agreement, VRF, sub-quadratic consensus protocol}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.28
Improved Extension Protocols for Byzantine Broadcast and Agreement

Authors: Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study extension protocols of BB and BA, i.e., protocols that solve BB/BA with long inputs of l bits using lower costs than l single-bit instances. We present new protocols with improved communication complexity in almost all settings: authenticated BA/BB with t < n/2, authenticated BB with t < (1-ε)n, unauthenticated BA/BB with t < n/3, and asynchronous reliable broadcast and BA with t < n/3. The new protocols are advantageous and significant in several aspects. First, they achieve the best-possible communication complexity of Θ(nl) for wider ranges of input sizes compared to prior results. Second, the authenticated extension protocols achieve optimal communication complexity given the current best available BB/BA protocols for short messages. Third, to the best of our knowledge, our asynchronous and authenticated protocols in the setting are the first extension protocols in that setting.
Cite as

Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved Extension Protocols for Byzantine Broadcast and Agreement. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nayak_et_al:LIPIcs.DISC.2020.28,
  author =	{Nayak, Kartik and Ren, Ling and Shi, Elaine and Vaidya, Nitin H. and Xiang, Zhuolun},
  title =	{{Improved Extension Protocols for Byzantine Broadcast and Agreement}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.28},
  URN =		{urn:nbn:de:0030-drops-131064},
  doi =		{10.4230/LIPIcs.DISC.2020.28},
  annote =	{Keywords: Byzantine agreement, Byzantine broadcast, extension protocol, communication complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.47
Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency

Authors: Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
This paper investigates the problem good-case latency of Byzantine agreement, broadcast and state machine replication in the synchronous authenticated setting. The good-case latency measure captures the time it takes to reach agreement when all non-faulty parties have the same input (or in BB/SMR when the sender/leader is non-faulty) and all messages arrive instantaneously. Previous result implies a lower bound showing that any Byzantine agreement or broadcast protocol tolerating more than n/3 faults must have a good-case latency of at least Δ. Our first result is a matching tight upper bound for a family of protocols we call 1Δ. We propose a protocol 1Δ-BA that solves Byzantine agreement in the synchronous and authenticated setting with optimal good-case latency of Δ and optimal resilience f < n/2. We then extend our protocol and present 1Δ-BB and 1Δ-SMR for Byzantine fault tolerant broadcast and state machine replication, respectively, in the same setting and with the same optimal good-case latency of Δ and f < n/2 fault tolerance.
Cite as

Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2020.47,
  author =	{Abraham, Ittai and Nayak, Kartik and Ren, Ling and Xiang, Zhuolun},
  title =	{{Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{47:1--47:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.47},
  URN =		{urn:nbn:de:0030-drops-131259},
  doi =		{10.4230/LIPIcs.DISC.2020.47},
  annote =	{Keywords: Byzantine broadcast, synchrony, latency, state machine replication}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.25
Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus

Authors: Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another chal- lenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.
Cite as

Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman. Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2017.25,
  author =	{Abraham, Ittai and Malkhi, Dahlia and Nayak, Kartik and Ren, Ling and Spiegelman, Alexander},
  title =	{{Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.25},
  URN =		{urn:nbn:de:0030-drops-86409},
  doi =		{10.4230/LIPIcs.OPODIS.2017.25},
  annote =	{Keywords: Cryptocurrency, Blockchain, Byzantine fault tolerance, Reconfiguration}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.41
Brief Announcement: Practical Synchronous Byzantine Consensus

Authors: Ittai Abraham, Srinivas Devadas, Kartik Nayak, and Ling Ren

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
This paper presents new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The PBFT state machine replication protocol tolerates f Byzantine faults in an asynchronous setting using n = 3f + 1 replicas. We improve the Byzantine fault tolerance to n = 2f + 1 by utilizing the synchrony assumption. Our protocol also solves synchronous authenticated Byzantine agreement in fewer expected rounds than the best existing solution (Katz and Koo, 2006).
Cite as

Ittai Abraham, Srinivas Devadas, Kartik Nayak, and Ling Ren. Brief Announcement: Practical Synchronous Byzantine Consensus. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 41:1-41:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2017.41,
  author =	{Abraham, Ittai and Devadas, Srinivas and Nayak, Kartik and Ren, Ling},
  title =	{{Brief Announcement: Practical Synchronous Byzantine Consensus}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{41:1--41:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.41},
  URN =		{urn:nbn:de:0030-drops-79703},
  doi =		{10.4230/LIPIcs.DISC.2017.41},
  annote =	{Keywords: consensus, agreement, Byzantine fault tolerance, replication, synchrony}
}
  • Refine by Author
  • 9 Nayak, Kartik
  • 8 Abraham, Ittai
  • 6 Ren, Ling
  • 3 Malkhi, Dahlia
  • 3 Xiang, Zhuolun
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 consensus
  • 4 synchrony
  • 3 Byzantine Fault Tolerance
  • 3 Byzantine broadcast
  • 3 communication complexity
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 3 2020
  • 3 2021
  • 3 2022
  • 1 2017
  • 1 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact