DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.8

Weaker Assumptions for Asymmetric Trust

Authors: Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract

In distributed systems with asymmetric trust, each participant is free to make its own trust assumptions about others, captured by an asymmetric quorum system. This contrasts with ordinary, symmetric quorum systems and threshold models, where trust assumptions are uniformly shared among participants. Fundamental problems like reliable broadcast and consensus are unsolvable in the asymmetric model if quorum systems satisfy only the classical properties of consistency and availability. Existing approaches overcome this by introducing stronger assumptions. We show that some of these assumptions are overly restrictive, so much so that they effectively eliminate the benefits of asymmetric trust. To address this, we propose a new approach to characterize asymmetric problems and, building upon it, present algorithms for reliable broadcast and consensus that require weaker assumptions than previous solutions. Our methods are general and can be extended to other core problems in systems with asymmetric trust.

Cite as

Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis. Weaker Assumptions for Asymmetric Trust. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2025.8,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Kamp, Simon Holmgaard and Villacis, Juan},
  title =	{{Weaker Assumptions for Asymmetric Trust}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.8},
  URN =		{urn:nbn:de:0030-drops-251812},
  doi =		{10.4230/LIPIcs.OPODIS.2025.8},
  annote =	{Keywords: Asymmetric Trust, Quorum Systems, Reliable Broadcast, Consensus}
}

Document

DOI: 10.4230/LIPIcs.AFT.2023.31

Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast

Authors: Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, and Jesper Buus Nielsen

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract

We present simple and practical protocols for generating randomness as used by asynchronous total-order broadcast. The protocols are secure in a proof-of-stake setting with dynamically changing stake. They can be plugged into existing protocols for asynchronous total-order broadcast and will turn these into asynchronous total-order broadcast with dynamic stake. Our contribution relies on two important techniques. The paper "Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography" [Cachin, Kursawe, and Shoup, PODC 2000] has influenced the design of practical total-order broadcast through its use of threshold cryptography. However, it needs a setup protocol to be efficient. In a proof-of-stake setting with dynamic stake this setup would have to be continually recomputed, making the protocol impractical. The work "Asynchronous Byzantine Agreement with Subquadratic Communication" [Blum, Katz, Liu-Zhang, and Loss, TCC 2020] showed how to use an initial setup for broadcast to asymptotically efficiently generate sub-sequent setups. The protocol, however, resorted to fully homomorphic encryption and was therefore not practically efficient. We adopt their approach to the proof-of-stake setting with dynamic stake, apply it to the Constantinople paper, and remove the need for fully homomorphic encryption. This results in simple and practical proof-of-stake protocols.

Cite as

Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, and Jesper Buus Nielsen. Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.AFT.2023.31,
  author =	{Alpos, Orestis and Cachin, Christian and Kamp, Simon Holmgaard and Nielsen, Jesper Buus},
  title =	{{Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.31},
  URN =		{urn:nbn:de:0030-drops-192203},
  doi =		{10.4230/LIPIcs.AFT.2023.31},
  annote =	{Keywords: Total-Order Broadcast, Atomic Broadcast, Proof of Stake, Random Beacon}
}

Search Results

Documents authored by Kamp, Simon Holmgaard

Weaker Assumptions for Asymmetric Trust

Abstract

Cite as

Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast

Abstract

Cite as

Thanks for your feedback!

Could not send message